Java最小堆优先队列实现

Question

我目前正在尝试实现一个最小堆优先队列，但是我的实现有一些问题，我似乎无法弄清楚我哪里做错了——它不能输出最低优先级或正确排序。

    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

我希望结果按升序排列 - 起初我认为可能是由于交换错误的子级，但最后一个输出是最高优先级，所以这没有意义。我花了几个小时研究堆优先队列，但找不到任何有用的信息。

编辑：以下是CMPS要求的代码更好的输出（我想这就是您要求的）。

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

- Craig

---

为什么不使用java.util.PriorityQueue呢？ - juhist

这是我要做的一项工作 - 我正在创建A*算法，需要这个来获得良好的性能。我被告知必须自己实现所有方面 - 我希望我可以简单地使用内置的算法！ - Craig

你能打印出这两行之间的数组内容吗：Array data: 543.0 PQ data: 8.0？ - CMPS

没关系，那就是我需要的，谢谢。 - CMPS

如果您的目标是良好的性能，请确保对您的实现进行基准测试，与内置实现进行比较。 - pjs

Answer 1

当你在移除一个节点后向下冒泡时，需要将最小值放在堆的顶部，但在以下代码中，如果最小值在顶部，则会进行交换，这应该是相反的方式。

更改：

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

- CMPS

---

我注意到当我使用更大的数据集时，与PQ中优先级最低的项目在错误的索引中相关的问题会进一步增加！似乎只有在队列中有大约30个以上的项目时才会发生。我很好奇，您是否还注意到我的代码中存在其他问题？ - Craig

@Craig，您能以与您的编辑相同的方式发布输出结果吗？ - CMPS

我一段时间前创建了这个新问题，其中可能提供了最好的细节：http://stackoverflow.com/questions/29412686/java-priority-queue-in-a-algorithm-issue - Craig

Answer 2

为了实现最小堆，您可以使用优先队列。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。希望能对您有所帮助。

- Mohammad