java如何迭代优先级队列？

Question

for (Event e : pq)

不按优先级顺序迭代

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

这可以工作，但会清空队列

Answer 1

从Javadocs

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

可能还有其他类似的机制

Answer 2

基于堆的优先级队列只保证第一个元素是最高/最低的。没有廉价的（即O（n））方法来获得排序形式的元素

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

Answer 3

您可以复制队列并在循环中轮询，在本例中，pq是原始优先级队列：

PriorityQueue<Your_class> pqCopy = new PriorityQueue<Your_class>(pq);
while(!pqCopy.isEmpty()){
    Your_Class obj = pqCopy.poll();
    // obj is the next ordered item in the queue
    .....
}

Answer 4

以前的海报上说，除了noone之外，其他人都给出了完整的工作示例（除了复制pq），所以这里是：

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

Answer 5

最近，我也有同样的问题。我想使用优先级队列中的某个特定对象，然后保留其余元素

1）我创建了一个newPriorityQueue。 2） 使用迭代器分析oldQueue中的每个元素 3） 使用旧队列。poll（）方法来检索元素 4） 如果未使用，请将元素3）插入newPriorityQueue

 Queue<String> newQueue = new PriorityQueue<String>(); 
    // Assuming that oldQueue have some data in it.

    Iterator<String> itr = oldQueue.iterator();
    while(itr.hasNext()){
        String str = oldQueue.poll();
        // do some processing with str
        if(strNotUsed){
            newQueue.offer(str);
        }
    }

最后，oldQueue将是空的。 @其他：-如果我能做同样的事情，请建议一个更好的方法。我不能使用迭代器，因为它没有以正确的顺序返回元素

Answer 6

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

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

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

要获得下一个元素，您必须将最小的顶层元素出列，这就是它的工作方式
Dequeing（re-heapify=O(log n)time）不仅仅是将该元素取出的问题，底层结构会重新安排自身，以便将优先级最低的元素放在第一位

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

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