Java中的排序优先队列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25569625/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting Priority Queue in Java
提问by apprentice
I was trying to insert the integers in PriorityQueue, and I know that :
我试图在 中插入整数PriorityQueue，我知道：
If no comparator is specified when a PriorityQueueis constructed, then the default
comparator for the type of data stored in the queue is used. The default comparator will order
the queue in ascending order
如果在PriorityQueue构造a 时未指定比较器，则使用存储在队列中的数据类型的默认比较器。默认比较器将按升序排列队列
However, the output I am getting is not in sorted order.
Output after running the below code is : [2, 4, 8, 6]
但是，我得到的输出不是按顺序排列的。运行以下代码后的输出是：[2, 4, 8, 6]
public static void main(String args[]) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
q.offer(4);
q.offer(2);
q.offer(8);
q.offer(6);
System.out.print(q);
}
Can someone please explain why ?
有人可以解释为什么吗？
采纳答案by Erik Vesteraas
A PriorityQueueis what is called a binary heap. It is only ordered/sorted in the sense that the firstelement is the least. In other word, it only cares about what is in the front of the queue, the rest are "ordered" when needed.
一个PriorityQueue的是所谓的二元堆。它仅在第一个元素最少的意义上进行排序/排序。换句话说，它只关心队列前面的内容，其余的在需要时“排序”。
The elements are only ordered as they are dequeued, i.e. removed from the queue using poll(). This is the reason why a PriorityQueue manages to have such good performance, as it is not doing any more sorting than it needs at any time.
元素仅在出队时进行排序，即使用poll(). 这就是 PriorityQueue 设法拥有如此出色性能的原因，因为它在任何时候都不会进行超出其需要的排序。
If you want to know how heaps work in detail I recommend this MIT lecture on heaps.
如果您想详细了解堆是如何工作的，我建议您阅读有关堆的麻省理工学院讲座。
回答by coffeeaddict
How java priority Queue is suppose to work?
Basically your print statement does not traverse the tree in order.
基本上你的打印语句不会按顺序遍历树。
回答by Florent Bayle
When you call System.out.print()on your PriorityQueue, it will not poll()your elements from it, but call toString(). PriorityQueuedoesn't implement toString(), so it's the toString()from AbstractCollectionwhich will be called:
当您调用System.out.print()您的 时PriorityQueue，它不会poll()从中调用您的元素，而是调用toString(). PriorityQueue没有实现toString()，所以它是toString()从AbstractCollection将被称为：
public String toString() {
Iterator<E> i = iterator();
if (! i.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = i.next();
sb.append(e == this ? "(this Collection)" : e);
if (! i.hasNext())
return sb.append(']').toString();
sb.append(", ");
}
}
As you can see, this method only iterate the PriorityQueue. As you can see in the PriorityQueuejavadoc:
如您所见，此方法仅迭代PriorityQueue. 正如您在PriorityQueuejavadoc 中看到的：
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
方法 iterator() 中提供的 Iterator 不保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray())。
If you want to use the PriorityQueueas it is intented to be used, you have to poll()each value and print it:
如果你想使用PriorityQueue它的意图，你必须使用poll()每个值并打印它：
while (!q.isEmpty()) {
Integer i = q.poll();
System.out.println(i);
}
Output:
输出：
2
4
6
8
回答by llogiq
That's because java.util.PriorityQueueimplements a binary heap.
那是因为java.util.PriorityQueue实现了一个二元堆。
Unfortunately, there is no easy way to sort a PriorityQueue. If you poll()objects until the queue is empty, the elements will be in the comparator's order. That's why when I was faced with a similar problem I've implemented my own heap class that allows me to sort the elements after the fact; which I use for a top N list of a large number of elements.
不幸的是，没有简单的方法来对 PriorityQueue 进行排序。如果您poll()一直反对直到队列为空，则元素将按比较器的顺序排列。这就是为什么当我遇到类似的问题时，我实现了自己的堆类，它允许我在事后对元素进行排序；我将其用于大量元素的前 N 个列表。
(Since I made the class on the job, I don't have the right to post it here, but it's largely modeled after python's heap.py, so there's a good source of inspiration)
（由于我是在工作中制作的课程，我无权在这里发布它，但它主要是仿照 python 的heap.py，所以有一个很好的灵感来源）
回答by evenprime
An unbounded priority queueis based on a priority heap
无界优先级队列基于priority heap
Priority Queue.Offer()method uses siftUpComparable()internally to insert items when passed without comparator
Priority Queue.Offer()方法siftUpComparable()在没有比较器的情况下传递时在内部使用以插入项目
siftUpComparablecompares current element with all elements at Parent Positions(int i = paramInt - 1 >>> 1;) until the Heap condition is met
siftUpComparable将当前元素与 Parent Positions( int i = paramInt - 1 >>> 1;)处的所有元素进行比较，直到满足 Heap 条件
siftUpComparableAlgorithm in Nutshell (if implemented through array Root=index 0):
siftUpComparableNutshell 中的算法（如果通过数组 Root=index 0 实现）：
1.Add the element to the bottom level of the heap.
2.Compare the added element with its parent; if they are in the correct order, stop.
3.If not, swap the element with its parent and return to the previous step.
Java Code
Java代码
private void siftUpComparable(int paramInt, E paramE)
{
Comparable localComparable = (Comparable)paramE;
while (paramInt > 0)
{
int i = paramInt - 1 >>> 1;
Object localObject = this.queue[i];
if (localComparable.compareTo(localObject) >= 0) {
break;
}
this.queue[paramInt] = localObject;
paramInt = i;
}
this.queue[paramInt] = localComparable;
}
In Your example:
在你的例子中：
q.offer(4);-> Inserts 4
q.offer(4);-> 插入 4
Result: PQ[0]=4
Result: PQ[0]=4
q.offer(2);-> siftUpComparablecompares 4 to 2 and swap positions (comparisons at Parent Locations)
q.offer(2);->siftUpComparable比较 4 到 2 并交换位置（在父位置进行比较）
Result: PQ[0]=2,PQ[1]=4
Result: PQ[0]=2,PQ[1]=4
q.offer(8);-> siftUpComparableCompares 8 and 2 (since 2 is at Parent Location)
q.offer(8);->siftUpComparable比较 8 和 2（因为 2 在父位置）
Result: PQ[2]=8
Result: PQ[2]=8
q.offer(6);: -> siftUp Compares 6 with 4 (Parent of location 3 is Location 1 according to paramInt - 1 >>> 1;logic )
q.offer(6);:-> siftUp 将 6 与 4 进行比较（根据paramInt - 1 >>> 1;逻辑，位置 3 的父级是位置 1 ）
Result: PQ[3]=6
Result: PQ[3]=6
Final PQ=[2, 4, 8, 6]
最终的 PQ=[2, 4, 8, 6]
