优先级队列在添加时未排序

sorting java priority-queue

2022-09-01 05:41:34

我有一个优先级队列，我在其中添加了一个 Node 对象，其中的节点应按它们包含的值进行排序。由于某种原因，优先级队列不会在添加时对节点进行排序。如果有人能看到这方面的问题或有任何指导，我将不胜感激。下面是一个简短示例：

PriorityQueue<Node> PQ = new PriorityQueue<Node>();
        //for each entry create a node and add it to the PriorityQueue
        for(Entry<Character,Integer> entry : entries){
            PQ.add(new Node(entry.getKey(),entry.getValue(), true));
        }

这是节点的方法：compareTo

@Override
public int compareTo(Node n) {
  if(n.frequency.intValue() > this.frequency.intValue()) return  -1;
  else if(n.frequency.intValue() == this.frequency.intValue()) return 0;
  else return 1;
}

答案 1

我猜您希望在迭代时以特定顺序返回元素。但是，不提供此类行为，因为它是作为优先级堆而不是排序列表实现的。来自 javadoc：PriorityQueuePriorityQueue

方法迭代器（）中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用 Arrays.sort（pq.toArray（））。

提供的唯一保证是、等返回最小元素。如果需要元素的有序迭代，请使用其他一些集合，例如 .PriorityQueuepoll()peek()TreeSet

答案 2

对于任何希望如何按照顺序迭代队列的人来说，这可以通过使用轮询或删除来实现。

while (!queue.isEmpty())
    System.out.println(queue.poll());

while (!queue.isEmpty())
    System.out.println(queue.remove());

和之间的唯一区别是，当为空时，poll 返回 null，而 remove 会抛出一个。poll()remove()NoSuchElementException