在Java中排序优先级队列

我试图在PriorityQueue插入整数，我知道：

如果在构造PriorityQueue时未指定比较器，则使用存储在队列中的数据类型的默认比较器。 默认比较器将按升序对队列进行排序

但是，我得到的输出不是按排序顺序。 运行以下代码后的输出为： [2, 4, 8, 6]

 public static void main(String args[]) { PriorityQueue q = new PriorityQueue(10); q.offer(4); q.offer(2); q.offer(8); q.offer(6); System.out.print(q); } 

有人可以解释一下原因吗？

Answer 1

PriorityQueue就是所谓的二进制堆 。 它只是在第一个元素最少的意义上排序/排序。 换句话说，它只关心队列前面的内容，其余部分在需要时“排序”。

元素仅在它们出列时排序，即使用poll()从队列中删除。 这就是为什么PriorityQueue能够获得如此优异的性能的原因，因为它不会在任何时候进行任何更多的排序。

如果你想知道堆是如何工作的，我推荐麻省理工学院的这个讲座 。

Answer 2

当您在PriorityQueue上调用System.out.print()时，它不会从中poll()您的元素，而是调用toString() 。 PriorityQueue没有实现toString() ，所以它是来自AbstractCollection的toString() ，它将被调用：

 public String toString() { Iterator 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(", "); } } 

如您所见，此方法仅迭代PriorityQueue 。 正如您在PriorityQueue javadoc中看到的：

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

如果您希望使用PriorityQueue因为它有意使用，您必须poll()每个值并打印它：

 while (!q.isEmpty()) { Integer i = q.poll(); System.out.println(i); } 

输出：

 2 4 6 8 

Answer 3

那是因为java.util.PriorityQueue实现了二进制堆 。

不幸的是，没有简单的方法来排序PriorityQueue。 如果poll()对象直到队列为空，则元素将按比较器的顺序排列。 这就是为什么当我遇到类似的问题时，我已经实现了自己的堆类，允许我在事后对元素进行排序; 我用于大量元素的前N列表。

（由于我在课堂上上课，我没有权利在这里发布，但它主要是在python的heap.py之后建模的，所以有很好的灵感来源）

Answer 4

无界优先级队列基于priority heap

Priority Queue.Offer()方法在内部使用siftUpComparable()在没有比较器的情况下传递项目

siftUpComparable将当前元素与Parent Positions（ int i = paramInt - 1 >>> 1; ）中的所有元素进行比较int i = paramInt - 1 >>> 1;直到满足Heap条件

---

Nutshell中的siftUpComparable算法（如果通过数组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代码

  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; } 

---

在你的例子中：

q.offer(4); – >插入4

Result: PQ[0]=4

---

q.offer(2); – > siftUpComparable比较4到2并交换位置（在父位置进行比较）

Result: PQ[0]=2,PQ[1]=4

---

q.offer(8); – > siftUpComparable比较8和2（因为2位于父位置）

Result: PQ[2]=8

---

q.offer(6); ： – > siftUp比较6和4（位置3的父级是位置1根据paramInt - 1 >>> 1;逻辑）

Result: PQ[3]=6

---

最终PQ=[2, 4, 8, 6]

Answer 5

java优先级队列如何工作？

基本上，您的print语句不会按顺序遍历树。