Java最小堆优先级队列实现

Question

我目前正在尝试实现min heap PQ，但是我在实现的正确性方面遇到了一些问题，我似乎无法找出我做错了什么——它没有输出最低优先级，也没有对它们进行正确排序。

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

使用以下测试数据：

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

我得到以下结果：

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

我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子，但最后一个输出是最大的优先级，所以这没有意义。我花了几个小时试图研究堆优先级队列，但我找不到任何帮助。

以下是CMP要求的更好的代码输出（我认为这是您要求的）

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 1

为了实现最小堆，您可以使用优先级队列。Java对这些数据结构有很好的支持。要按优先级队列实现最小堆，请尝试以下方式：

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()+" ");
        }
    }

}

有关更多信息，请访问：https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MinHeapWithPriorityQueue.java.我希望有帮助。

Answer 2

当您删除一个节点后在堆中冒泡时，您需要在顶部有最小值，但是在下面的代码中，如果最小值在顶部，您就是在交换，这应该是相反的方式。

更改：

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

致：

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