如何迭代优先级队列？

loops collections java priority-queue

2022-09-01 01:23:49

for (Event e : pq)

不按优先级顺序迭代。

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

这有效，但会清空队列。

答案 1

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

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

偷看（读取堆中的顶部元素堆）是恒定时间，因为它查看最小的元素。O(1)

要获得下一个元素，您必须将最小的顶部元素排出队列，这就是它的工作原理。
去排队（重新堆=时间）不仅仅是取出该元素的问题，底层结构会重新排列自己，以便首先使优先级最低的元素。O(log n)

此外，要遍历整个优先级队列以按排序顺序读取所有项目，这是一个操作。
因此，您不妨抓住队列中的所有元素并对其进行排序（也），然后您可以根据需要浏览它们。唯一的缺点是您持有队列的额外副本。O(n log(n))O(n log (n))

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

答案 2

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

可能还有其他等效机制。