如何遍历 PriorityQueue？

Question

for (Event e : pq)

不按优先顺序迭代。

 while(!pq.isEmpty()){
  Event e = pq.poll();
}

这有效但清空了队列。

原文由 simpatico 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

来自 Javadocs

方法中提供的迭代器 iterator() 不保证以任何特定顺序遍历 PriorityQueue 的元素。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray()) 。

可能还有其他等效机制。

原文由 Oliver Charlesworth 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

由于底层实现（我认为它是 Java 中的最小堆），您不能按该顺序遍历 Priority Queue 。

它不是排序数组， 因此您可以从一个元素转到优先级较低的元素。

peeking（读取堆中堆顶元素）是常数时间 O(1) 因为它看的是最小的元素。

要获得第二个下一个，您 必须 使最小的顶部元素出列，这就是它的工作原理。

Dequeing (re-heapify = O(log n) time) 不仅仅是取出该元素的问题，底层结构会重新排列自身，以便首先带来优先级最低的元素。

此外，遍历整个优先级队列以按排序顺序读取所有项目，这是一个 O(n log(n)) 操作。

所以你也可以只抓取队列中的所有元素并对它们进行排序（也 O(n log (n)) ）然后你可以按照你的意愿浏览它们。唯一的缺点是您持有队列的额外副本。

尽管如此，如果您需要以这种方式遍历数据，优先级队列可能不是满足您需要的正确数据结构。

原文由 Alex Florescu 发布，翻译遵循 CC BY-SA 4.0 许可协议