Java Min Heap Priority Queue Implementation

Question

I'm currently trying to implement a min heap PQ, however I'm having some issues regarding the correctness of my implementation and I can't seem to figure out what I'm doing wrong - it doesn't output the lowest priority or sort them properly.

    public void AddItem(Vertex item)
  {    
      if (queueSize == QueueArray.length)
      {
          Vertex[] QueueArray2 = new Vertex[queueSize*2];          
          System.arraycopy(QueueArray, 0, QueueArray2, 0, queueSize);           
          QueueArray = QueueArray2;         
      }

    if (queueSize == 0)
    {
      QueueArray[queueSize] = item; // insert at 0
      queueSize++;
    }
    else
    {
        int index=queueSize;
        //Vertex newNode = new Vertex(item, priority);
        QueueArray[index] = item;
        queueSize++;

        int parent=(index-1)/2;
        while (index!=0 && QueueArray[index].getF()<QueueArray[parent].getF())
        {
            // swap parent and index items
            Vertex temp = QueueArray[parent];
            QueueArray[parent] = QueueArray[index];
            QueueArray[index] = temp;

            index=parent;
            parent=(index-1)/2;
        } 
    }     
  }


  public Vertex GetNextItem()
  {
      if (queueSize == 0)
      {
          return null;
      }
      Vertex temp = QueueArray[0];
      --queueSize;
      if (queueSize > 0)
      {
         QueueArray[0] = QueueArray[queueSize];
         swapNodes(0);
      }
      QueueArray[queueSize] = null;
      return temp;
   }

   public void swapNodes(int root)
   {
      int child;                        
      if ((2*root+1) >= queueSize)
      {
         child = root;        //no children
      }
      else 
          if ((2*root)+2 == queueSize)
          {
                child = (2*root)+1;     
          }
          else 
            if (QueueArray[(2*root)+1].getF()< QueueArray[(2*root)+2].getF())
            {
                 child = (2*root)+1;   //left child  
            }
            else
            {
                 child = (2*root)+2;     //right child
            }
      //swap the nodes around
      if (QueueArray[root].getF() < QueueArray[child].getF())
      {
         Vertex temp = QueueArray[root];
         QueueArray[root] = QueueArray[child];
         QueueArray[child] = temp;
         swapNodes(child);
      }
   }

Using the following test data:

data1.setF(71);
data2.setF(19);
data3.setF(65);
data4.setF(16);
data5.setF(14);
data6.setF(8);
data7.setF(10);
data8.setF(36);
data9.setF(543);
test.AddItem(data1);
test.AddItem(data2);
test.AddItem(data3);
test.AddItem(data4);
test.AddItem(data5);
test.AddItem(data6);
test.AddItem(data7);
test.AddItem(data8);
test.AddItem(data9);

I get the following results:

Array data: 8.0 
Array data: 16.0 
Array data: 10.0 
Array data: 36.0   
Array data: 19.0 
Array data: 65.0 
Array data: 14.0 
Array data: 71.0   
Array data: 543.0 
PQ data: 8.0 
PQ data: 543.0 
PQ data: 71.0 
PQ data: 14.0 
PQ data: 65.0
PQ data: 19.0
PQ data: 36.0 
PQ data: 16.0
PQ data: 10.0

I'm expecting the results to be in ascending order - at first I thought it may be due to the wrong children being swapped but then the last output is the greatest priority so that didn't make sense. I've spent a few hours trying to research Heap priority queues but I can't find anything to help.

Edit:

Here is a better output of the code as asked by CMPS (I think this is what you asked for)

Array data: 8.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
Array data: 71.0
Array data: 543.0
PQ GetNextItem: 8.0

Array data: 543.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
Array data: 71.0
PQ GetNextItem: 543.0

Array data: 71.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
Array data: 14.0
PQ GetNextItem: 71.0

Array data: 14.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
Array data: 65.0
PQ GetNextItem: 14.0

Array data: 65.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
Array data: 19.0
PQ GetNextItem: 65.0

Array data: 19.0
Array data: 16.0
Array data: 10.0
Array data: 36.0
PQ GetNextItem: 19.0

Array data: 36.0
Array data: 16.0
Array data: 10.0
PQ GetNextItem: 36.0

Array data: 16.0
Array data: 10.0
PQ GetNextItem: 16.0

Array data: 10.0
PQ GetNextItem: 10.0

It's for a piece of work I have to do - I'm creating the A* Algorithm and require this to get decent performance. I've been told I have to implement all aspects myself - I wish I could simply use the inbuilt one! — Craig
– Craig, Commented Apr 1, 2015 at 14:11
Can you print the array content between these 2 lines : Array data: 543.0 PQ data: 8.0 — CMPS
– CMPS, Commented Apr 1, 2015 at 14:43
@CMPS I've edited my original post with what I think you asked for — Craig
– Craig, Commented Apr 1, 2015 at 14:47
Why is the PQ GetNextItem giving different result in your original output and the new added one ? — CMPS
– CMPS, Commented Apr 1, 2015 at 14:52

CMPS · Accepted Answer · 2015-04-01 15:03:28Z

1

When you bubble down in the heap after removing a node, you need to have the minimum at the top, but in the following code, you are swapping if the minimum is in the top, which should be the opposite way.

Change:

     if (QueueArray[root].getF() < QueueArray[child].getF())
      {
         Vertex temp = QueueArray[root];
         QueueArray[root] = QueueArray[child];
         QueueArray[child] = temp;
         swapNodes(child);
      }

To:

      if (QueueArray[root].getF() > QueueArray[child].getF())
      {
         Vertex temp = QueueArray[root];
         QueueArray[root] = QueueArray[child];
         QueueArray[child] = temp;
         swapNodes(child);
      }

answered Apr 1, 2015 at 15:03

CMPS

7,7874 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Craig Over a year ago

I've noticed that when I use larger data sets I get further issues relating to items in the PQ with the lowest priority being in the wrong index! It seems to only happen when there is about 30+ items in the queue. I'm curious; was there any other issue with my code that you noticed?

CMPS Over a year ago

@Craig can you post the output the same way you did in your edit

Craig Over a year ago

I created this new question a while ago which probably gives the best detail: stackoverflow.com/questions/29412686/…

Vahid · Accepted Answer · 2016-09-24 21:41:34Z

In order to implement min heap, you can use priority queue. Java has good support for these data structures. For implementing a min heap by priority queue, try this:

import java.util.PriorityQueue;

public class MinHeapWithPriorityQueue {

    public static void main(String args[]) {
        // create priority queue
        PriorityQueue< Integer > prq = new PriorityQueue <> ();

        // insert values in the queue
        prq.add(6);
        prq.add(9);
        prq.add(5);
        prq.add(64);
        prq.add(6);

        //print values
        while (!prq.isEmpty()) {
            System.out.print(prq.poll()+" ");
        }
    }

}

For more information, please visit: https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MinHeapWithPriorityQueue.java. I hope it helps.

Collectives™ on Stack Overflow

Java Min Heap Priority Queue Implementation

Edit:

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Edit:

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related