优先队列的顺序错误。

Question

我遇到了一个与Java 8和Intellij Idea中PriorityQueue顺序相关的问题，当我将第三个数字添加到队列中时，顺序错误，但只有第三个数字存在此问题，以下是我的代码。

import java.util.*;

public class vector {
    static Queue<Integer> q=new PriorityQueue<Integer>();
    public static void addNum(int num) {
        q.add(num);
    }
    public static void main(String args[]) {
        addNum(-1);
        addNum(-2);
        addNum(-3);
        addNum(-4);
        addNum(-5);
    }
}

我尝试调试代码，在 addNum(-3) 后，队列为 -3，-1，-2，但在 addNum(-4) 后，队列变成了 -4，-3，-2，-1。

- 张天禹

---

你所说的“队列是-3，-1，-2”是什么意思？你是如何观察到它的？ - Jon Skeet

@JonSkeet 我在对 OP 的示例代码中的 PQ 进行简单迭代时看到了这种行为。 - Tim Biegeleisen

你只能保证每个轮询的最小值，因为保存在其中的数据结构不是数组或队列，而是二叉小顶堆。这样添加和删除是最快的。 - Tim Biegeleisen

Java使用隐式二叉堆存储在数组中来实现PriorityQueue。请参阅https://en.wikipedia.org/wiki/Binary_heap，了解树如何映射到数组的完整描述及其原因。该数组***不是***完全有序的，唯一的保证是最小元素位于前面。维基百科文章有很好的插图，说明了这个过程的确切工作方式。 - pjs

Answer 1

PriorityQueue的合约并不能保证迭代顺序，而是保证从优先队列中移除的每个元素将遵循队列类型的自然排序或者提供了定制比较器的排序。 Javadoc对您所看到的内容进行了评论：

队列通常会以FIFO（先进先出）的方式排序元素，但也不一定如此。例外情况包括按照提供的比较器或元素的自然排序来排序元素的优先级队列，以及按LIFO（后进先出）的方式排列元素的LIFO队列（或堆栈）。

Java实现的优先队列契约是，从队列中移除的第一个元素将遵循队列中对象的自然顺序，或使用定制比较器（如果提供了）进行排序。

如果我们向您当前的脚本添加删除添加的五个元素的代码，我们将看到返回的项目将按从最小到最大的顺序排列：

public static void main(String args[]) {
    addNum(-1);
    addNum(-2);
    addNum(-3);
    addNum(-4);
    addNum(-5);

    // now remove all elements
    while (!q.isEmpty()) {
        System.out.println(q.remove());
    }
}

这将打印：

-5
-4
-3
-2
-1

如果你需要一个维护排序顺序的集合，那么考虑使用类似 TreeSet 的东西。或者，您可以使用普通的 ArrayList，然后调用Collections.sort()来强制实施特定的顺序。

- Tim Biegeleisen

---

我认为你没有解释清楚“我尝试调试代码，在addNum（-3）之后，队列是-3，-1，-2”的部分……这可能是让OP感到困惑的地方。（这不是一个非常清晰的问题。） - Jon Skeet

@JonSkeet 我正在更新。 - Tim Biegeleisen

Answer 2

如其他答案所暗示的那样，如果您希望按正确顺序检索元素，则应使用queue.poll()，例如：

    List<E> entities = new ArrayList<>();
    while(!queue.isEmpty()){
        entities.add(queue.poll());
    }

entities 列表中实体的顺序将按预期排序。

原因：Java PriorityQueue 仅确保实体入队的顺序，而不是在底层集合中迭代的顺序。

这些实体被映射到底层集合 "unsorted" 上，这意味着如果您尝试使用流访问这些实体：

queue.stream().collect(Collectors.toList());

或者一个迭代器：

Iterator<E> i = queue.iterator();
...
E e = i.next()

或者使用其他方法，例如queue.forEach()，或者在IDE调试器中观察您的队列，都不能保证使用任何这些方法获取的集合条目的顺序。

- Nestor Milyaev

Answer 3

PriorityQueue 的实现是基于优先堆的实现，而不是基于排序列表。

在 iterator() 方法中提供的迭代器不能保证以任何特定顺序遍历优先队列的元素。 如果需要有序遍历，请使用类似以下方法：

Arrays.sort(q.toArray());
for (Integer data :q) {
  System.out.println(data);
}

- TechFree

Answer 4

这是最常见的问题，许多集合框架如ArrayList、LinkedList等等，但在PriorityQueue中，当您打印元素时，它将按排序顺序排列，并遵循MIN_HEAP属性或者说基本上可以说Priority Queue是基于Min Heap Property实现的。因此，首先要理解MinHeap，然后再实现代码。

- Pranjal Rajput