Java优先级队列需要帮助

Question

我正在这里处理旅行推销员问题，但我的 p 队列没有运行，它只是简单地获取最后添加的项目。我想知道是否有人可以帮助我找出错误。这是我的 Node 类（添加到队列中的节点）：

import java.util.*; 

public class Node implements Comparable< Node >{

    //level of node
    int level;
    //stores path of node
    ArrayList< Integer > path = new ArrayList< Integer >();
    //bound of node
    int bound;

    /** Over-rides compareTo for priority queue handling
       * @return int desired sorting value
       */
    public int compareTo(Node aNode) 
    {               
      if (this.bound<aNode.bound)
      {
          return 1;
      }
      if (this.bound>aNode.bound)
      {
          return -1;
      }
      else
      {
          return 0;
      }
    }
}

这是 p 队列实现：

PriorityQueue< Node > theQ = new PriorityQueue< Node >();

该算法实现正确，p 队列根本没有将最低界限作为头。我什至反转了compareTo的返回，对p队列输出没有影响（对我来说，队列没有排序。我浪费了几个小时试图弄清楚它，还询问了一些同学（没有人能辨别出问题）在这里拍摄一下，看看是否有人知道为什么队列会这样。

Answer 1

你的代码对我来说工作得很好。

我怀疑您正在做的是更改单个对象的绑定值并重复添加它，为您提供一个充满同一对象的队列（对它有很多引用），当然它具有您设置的单个（最后一个）值。

public static void main(String[] args)
{
    PriorityQueue< Node > theQ = new PriorityQueue< Node >();
    Node n = new Node();
    n.bound = 6;
    theQ.add(n);
    n = new Node();
    n.bound = 9;
    theQ.add(n);
    n = new Node();
    n.bound = 4;
    theQ.add(n);
    while ((n = theQ.poll()) != null)
        System.out.println("Bound = " + n.bound);
}

输出：

绑定 = 9
绑定 = 6
绑定 = 4

Answer 2

确保您正在迭代 PriorityQueue使用 Queue 接口提供的方法，前任。 remove 将元素从顶部弹出。在伪代码中：

for each element in some other collection
  priorityQueue.add(element)

while priorityQueue is not empty
 Set node to priorityQueue.remove()
 Do stuff with node

如果您尝试迭代 for-each 循环或 PriorityQueue.iterator：

方法中提供的Iterator
iterator() 不保证
遍历优先级的元素
以任何特定顺序排队。

或者，如果您不想销毁/删除 PriorityQueue 中的元素以按顺序迭代，您可以使用，如文档所示，

  Arrays.sort(pq.toArray())