blocks|key|514739|text|基于堆的优先级队列只保证第一个元素是最高/最低的。没有廉价(即O(n))的方法来获得排序形式的元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|514740|如果您需要经常这样做，请考虑使用以排序形式维护元素的结构。例如，使用java.util.TreeSet，并使用pollFirst()或pollLast()代替peek()+/+poll()|offset|length|style|CODE|514741|entityMap|0|LINK|mutability|MUTABLE|url|http://download.oracle.com/javase/6/docs/api/java/util/NavigableSet.html#pollFirst%2528%2529^0|0|Y|H|1J|B|1V|A|27|6|2G|6|1J|B|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@$D|R|E|S|F|G]|$D|T|E|U|F|G]|$D|V|E|W|F|G]|$D|X|E|Y|F|G]|$D|Z|E|10|F|G]]|9|@$D|11|E|12|1|13]]|A|$]]|$1|H|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

A heap based priority queue only guarantees that the first element is the highest/lowest. There is no cheap (i.e. O(n)) way to get the elements in sorted form.

If you need to do this often, consider using a structure that maintains the elements in sorted form. For example, use <code>java.util.TreeSet</code>, and use either <a href="http://download.oracle.com/javase/6/docs/api/java/util/NavigableSet.html#pollFirst%28%29"><code>pollFirst()</code></a> or <code>pollLast()</code> in place of <code>peek()</code> / <code>poll()</code>

blocks|key|731336|text|之前的帖子说了所有的事情，但没有人给出完整的工作示例(除了复制pq)，所以这里是：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|731337|Event[]+events+=+pq.toArray(new+Event[pq.size()]);
Arrays.sort(events,+pq.comparator());
for+(Event+e+:+events)+{
++++System.out.println(e);
}|code-block|syntax|javascript|731338|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Previous posters said everything but noone gave full working example (other than copying pq), so here it is:

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

blocks|key|514824|text|您可以在循环中复制队列和轮询，在此示例中，pq是原始优先级队列：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|514825|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
++++.....
}|code-block|syntax|javascript|514826|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

You can make a copy of the queue and poll in a loop, in this example pq is the original priority queue:

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

blocks|key|731193|text|最近，我也遇到了同样的问题。我想使用优先级队列中的一些特定对象，然后保留剩余的元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|731194|1)我创建了newPriorityQueue。2)使用迭代器解析oldQueue中的每个元素3)使用oldQueue.poll()方法检索元素4)如果不使用，则将元素3)插入newPriorityQueue。|731195|+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);
++++++++}
++++}|code-block|syntax|javascript|731196|最后，oldQueue将为空。@Other：-如果我可以做同样的事情，请建议一个更好的方法。我不能使用迭代器，因为它没有按正确的顺序返回元素。|731197|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Recently, I had same problem. I wanted to use some particular object from the priority queue and then keep remaining elements preserved.

1) I created a newPriorityQueue.
2) Used Iterator to parse every element in oldQueue
3) used oldQueue.poll() method to retrieve the element
4) insert the element 3) to newPriorityQueue if not used.

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

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

In the end, oldQueue will be empty.
@ Others : - please suggest a better way if I can do the same thing. I can not use the iterator as it does not return elements in the correct order.

blocks|key|731290|text|因此，如上所述，将priorityQueue放在列表中，然后对其进行排序是一个很好的选择。以下是迭代器产生意外结果的一些细节：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|731291|迭代器不会以正确的顺序返回元素，因为它从底层数据结构打印(类似于ArrayList)。ArrayList中存储数据的方式与在BinaryHeap的数组实现中存储数据的方式相同。例如：|731292|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:-+"%2Bpq);+[2,+6,+7,+12,+9]|code-block|syntax|javascript|731293|其中childOf(i)是2*i%2B1和2*i%2B2，parentOf(i)是(i-1)/2|731294|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

So taking the priorityQueue in a List and then sorting it is a good option as mentioned above. Here are some details why the iterator gives unexpected results:

The iterator does not return elements in the correct order because it prints from the underlying data structure (similar to ArrayList). The ArrayList has data stored in it in the same way the data is stored in an Array implementation of BinaryHeap. For example: 

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

where childOf(i) is 2*i+1 and 2*i+2 and parentOf(i) is (i-1)/2

blocks|key|514982|text|受@carlos-cuesta思想的启发，在不消耗原始PriorityQueue的情况下构造排序迭代器实际上非常容易。例如，我们可以将其表示为kotlin中的扩展函数：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|514983|fun+<E>+PriorityQueue<E>.sortedIterator()+=+sequence+{
++++val+pqCopy+=+PriorityQueue(this@sortedIterator)

++++while(pqCopy.isNotEmpty())+yield(pqCopy.poll())
}

somePQ.sortedIterator().next()+//+...|code-block|syntax|javascript|514984|成功的关键是使用内置的复制构造函数复制优先级队列，然后再从它进行轮询。|514985|我相信这也比situtations中的大多数其他提供的解决方案更有效率，在situtations中，不仅仅是消耗完整的迭代器。|514986|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/41349854/590437^0|1|E|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@$A|V|B|W|1|X]]|C|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|C|$]]|$1|K|3|L|5|6|7|10|8|@]|9|@]|C|$]]|$1|M|3|-4|5|6|7|11|8|@]|9|@]|C|$]]]|N|$O|$5|P|Q|R|C|$S|T]]]]

Inspiried by the idea from <a href="https://stackoverflow.com/a/41349854/590437">@carlos-cuesta</a>, its actually very easy to construct a sorted iterator without consuming the orignal PriorityQueue. E.g. we can express this as an extension function in kotlin:
<pre class="lang-kotlin prettyprint-override"><code>fun &lt;E&gt; PriorityQueue&lt;E&gt;.sortedIterator() = sequence {
 val pqCopy = PriorityQueue(this@sortedIterator)

 while(pqCopy.isNotEmpty()) yield(pqCopy.poll())
}

somePQ.sortedIterator().next() // ...
</code></pre>
The key to success is copying the priority-queue with the built-in copy-constructor before polling from it.
I believe this is also more efficient than most of the other provided solutions in situtations where not just the complete iterator is being consumed.

blocks|key|514691|text|peek()方法不会从队列中删除任何内容，但正因为如此，它将不断获得顶部的值，直到它为空。我猜您在while循环之后检查了它是否为空，这将给出这个结论。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|514692|要做到这一点，唯一的方法就是自己排序。你可以像这样获得它的原始比较器：|514693|Event[]+events+=+Arrays.sort(pq.toArray(),+pq.comparator());
for+(Event+e+:+events)+{
++++//+do+stuff
}|code-block|syntax|javascript|514694|entityMap^0|0|6|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|R|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|S|8|@]|D|@]|E|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

The <code>peek()</code> method does not remove anything from the queue, but because of this, it will continually get the top value until it IS empty.
I'm guessing you checked if it was empty after your while loop, which would give you this conclusion.

The only way to do this is to sort it yourself.
You can get the original comparator for it like this:

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

blocks|key|731237|text|for+(Event+event:+pq.toArray(new+Event[pq.size()]))+{
++++event.toString();
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|731238|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>for (Event event: pq.toArray(new Event[pq.size()])) {
 event.toString();
}
</code></pre>

<pre><code>for (Event e : pq)
</code></pre>

doesn't iterate in the priority order.

<pre><code>while(!pq.isEmpty()){
 Event e = pq.poll();
}
</code></pre>

This works but empties the queue.

How to iterate over a PriorityQueue?

数据结构

for (Event e : pq)不按优先级顺序迭代。while(!pq.isEmpty()){  Event e = pq.poll();}这是可行的，但是清空了队列。

问如何在PriorityQueue上迭代？
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在PriorityQueue上迭代？EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在PriorityQueue上迭代？
EN