如何迭代PriorityQueue？

for (Event e : pq)

不会按优先级顺序迭代。如何迭代PriorityQueue？

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

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

来源

2011-11-14 simpatico

如何该空队列？ 'peek（）'不会删除元素。 –

peek（）'不应该删除对象 –

peek（）继续返回头部虽然 – simpatico

从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()) .

可能有其他类似机制。

来源

2011-11-14 22:32:16

这个答案会受益于一个例子。就我所知，'Arrays.sort（pq.toArray（））'什么也不做。首先必须创建一个数组来保存'PriorityQueue'的元素，然后可以使用'Arrays.sort（theActualArray，pq.comparer（））'对数组进行排序。 – Madmenyo

peek()方法不会从队列中删除任何内容，但是因为这个原因，它将不断获取顶部值，直到它为空。我猜你在while循环后检查它是否为空，这会给你这个结论。

要做到这一点的唯一方法是自己排序。你可以得到原来的比较它是这样的：

Event[] events = Arrays.sort(pq.toArray(), pq.comparator()); 
for (Event e : events) { 
    // do stuff 
}

来源

2011-11-14 22:31:54 xthexder

这与OP的原始示例相同。 –

+1表示完整示例 – Webnet

我已经了解到此示例不是最佳路线。使用“比较器”，不需要将队列转换为数组。（事件e：pq）{'应该完成这项工作。 – Webnet

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

如果您需要经常这样做，请考虑使用一种维护排序形式的元素的结构。例如，使用java.util.TreeSet，并在适当位置使用任何pollFirst()或pollLast()的peek()/poll()

来源

2011-11-14 22:36:55

不能按顺序遍历，因为底层实现的优先级队列（我认为这是在Java中最小堆）。它不是一个排序数组，因此您可以从一个元素转到具有较低优先级的元素。偷看是恒定的时间，因为它看起来最小的元素。要获得下一个（在O（log n）时间），您必须将最小的元素出列，这就是它的工作原理。离队不仅仅是把这个元素拿出来的问题，底层结构重新排列，以便首先将最低优先级的元素。

另外，要经历整个优先级队列是O（n log（n））操作。所以你可能只需要抓取队列中的所有元素并对它们进行排序（还有O（n log（n））），然后你可以按照你的意愿去完成它们。唯一的缺点是你持有队列的额外副本。

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

来源

2011-11-14 22:40:35

所以'PriorityQueue'几乎没用，然后呢？ – Qix

完全没有，它非常有用，并且非常适合它的实际意义。创建比完全排序的数据结构更快（线性vs O（n log n）），但您仍然可以在常量时间内找到最小/最大值，并以log n排队/出队。如果您需要按所有元素的排序顺序进行迭代，那么它就不是正确的数据结构。 –

公平，尽管我会尽量说它有相当有限/特定用途。 – Qix

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

1）我创建了一个newPriorityQueue。 2）用迭代器解析oldQueue中的每个元素 3）使用oldQueue.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将是空的。 @其他： - 如果我可以做同样的事情，请建议更好的方法。我不能使用迭代器，因为它不会以正确的顺序返回元素。

来源

2014-09-15 14:32:34 novice

可以使队列和民意调查的副本在一个循环，在这个例子中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 
    ..... 
}

来源

2016-12-27 17:53:28

-1

for (Event event: pq.toArray(new Event[pq.size()])) { 
    event.toString(); 
}

来源

2017-04-22 00:07:14

请编辑您的答案以包含一些解释。仅有代码的答案对未来SO读者的教育很少。您的回答是在低质量的审核队列中。 – mickmackusa

您的代码无法解决问题。数组应在迭代之前排序。 – Nolequen

所以服用时Queue中的列表，然后排序是如上所述的一个很好的选择。这里有一些细节为什么迭代器会给出意想不到的结果：

迭代器不以正确的顺序返回元素，因为它从底层数据结构（类似于ArrayList）打印。 ArrayList存储数据的方式与数据存储在BinaryHeap的Array实现中的方式相同。例如：

PriorityQueue<Integer> pq = new PriorityQueue<>(); 
ArrayList<Integer> test = new ArrayList(Arrays.asList(6,12,7,9,2)); 
test.forEach(x -> pq.add(x)); 
System.out.println("Priority Queue:- "+pq); [2, 6, 7, 12, 9]

其中childOf（i）是2 * i + 1的和2 * I + 2和parentOf（i）是第（i-1）/ 2

来源

2018-01-09 20:52:11

如何迭代PriorityQueue？

回答

相关问题