Craig Craig - 2 months ago 22
Java Question

Java Min Heap Priority Queue Implementation

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

Answer

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);
      }