如何迭代PriorityQueue？

Question

for (Event e : pq)

不按优先级顺序迭代.

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

这可以工作但排空队列.

Answer 1

来自Javadocs:

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

可能还有其他等效机制.

Answer 2

由于底层实现,您无法按顺序遍历优先级队列(我认为它是Java中的min-heap).它不是一个排序数组,因此您可以从一个元素转到具有较低优先级的元素.偷看是恒定的时间,因为它看着最小的元素.要获得下一个(在O(log n)时间内),您必须将最小元素出列,这就是它的工作原理.Dequeing不仅仅是将该元素取出,底层结构重新排列,以便首先将元素放在最低优先级.

此外,遍历整个优先级队列的是O(n log(n))操作.所以你也可以抓住队列中的所有元素并对它们进行排序(也是O(n log(n))),然后你可以按照自己的意愿进行排序.唯一的缺点是你持有队列的额外副本.

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

Answer 3

基于堆的优先级队列仅保证第一个元素是最高/最低.没有便宜的(即O(n))方式来获取排序形式的元素.

如果您需要经常这样做,请考虑使用以排序形式维护元素的结构.例如,使用java.util.TreeSet和使用pollFirst()或pollLast()代替peek()/poll()

Answer 4

之前的发帖者已经说了一切，但没有人给出完整的工作示例（除了复制 pq），所以这里是：

Event[] events = pq.toArray(new Event[pq.size()]);
Arrays.sort(events, pq.comparator());
for (Event e : events) {
    System.out.println(e);
}