在Java中对优先队列进行排序

Question

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

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

然而，我得到的输出结果没有按排序顺序排列。 运行下面的代码后，输出是：[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);
}

有人可以解释一下为什么吗？

- Apprentice

---

只有在从优先队列中弹出元素时，该顺序才有效。 - Heejin

Answer 1

一个优先队列(PriorityQueue)是一种称为二叉堆(binary heap)的数据结构。它仅按照第一个元素的大小进行排序。换句话说，它只关心队列的最前面有什么，而其他元素则在需要时“排序”。

元素仅在从队列中取出或使用poll()方法移除时排序。这也是优先队列能够实现良好性能的原因之一，因为它不会在任何时候都进行额外的排序。

如果您想详细了解堆的工作原理，我建议观看这个MIT关于堆的讲座。

- Erik Vesteraas

---

“按照它们出队的顺序排序”这正是我所寻找的，但显然并不正确：https://dev59.com/hmw05IYBdhLWcg3w6F8w正如你发现的那样，优先队列在添加或删除元素时不会重新排序所有元素。 - jMan

@jMan：这是正确的，但可能不够明确：元素按它们被出队的顺序排序，但唯一的保证是出队的元素在出队时是最小的。任何剩余的元素确实不会通过出队操作进行排序。 - Erik Vesteraas

Answer 2

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

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(", ");
}
}

正如您所看到的，这种方法仅迭代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

- Florent Bayle

Answer 3

那是因为 java.util.PriorityQueue 实现了一个二叉堆。

不幸的是，没有一种简单的方法可以对 PriorityQueue 进行排序。如果你使用 poll() 来取出对象直到队列为空，则元素将按照比较器的顺序排列。这就是当我面临类似问题时，我实现自己的堆类来允许我在事后对元素进行排序的原因；我用它来处理大量元素的前 N 个列表。

（由于我是在工作中制作的这个类，我没有在此发布它的权利，但它很大程度上是模仿 python 的heap.py，所以有一个很好的灵感来源）

- llogiq

Answer 4

一个无边界的优先级队列基于优先级堆

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

siftUpComparable将当前元素与父位置(int i = paramInt - 1 >>> 1;)的所有元素进行比较，直到满足堆条件为止。

---

siftUpComparable算法概述（如果通过数组实现，根节点为索引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 结果：PQ[0]=4

---

q.offer(2); -> siftUpComparable 将4和2进行比较并交换位置（在父节点位置进行比较）

结果：PQ[0]=2，PQ[1]=4

---

q.offer(8); -> siftUpComparable 比较8和2（因为2在父节点位置）

结果: PQ[2]=8

---

q.offer(6);: -> siftUp 将6与4进行比较（根据paramInt - 1 >>> 1;逻辑，位置3的父节点是位置1），进行上滤操作。

Result: PQ[3]=6

---

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

- Ravi Yenugu

Answer 5

Java 优先队列应该如何工作？

基本上，你的打印语句没有按顺序遍历树。

- coffeeaddict

---

@Bergi 不完全准确。print() 遍历树的底层数组，按照数组的顺序而非树的顺序。该树是部分有序的。 - user207421