Java中优先队列的顺序是什么？

Question

我不理解Java中PriorityQueue的排序顺序。据我了解，它们是基于堆的，无法按照插入顺序提供精确的迭代顺序。我想知道它们按照什么基准进行排序。

给定代码：

PriorityQueue<String> pq = new PriorityQueue<String>();
        pq.offer("hepqo");
        pq.offer("bro");
        pq.offer("wassup");
        pq.offer("okay");
        pq.offer("bingo");
        pq.offer("first");
        pq.offer("last");
        pq.offer("ssup");
        System.out.println("polled "+pq.poll());
        System.out.println(pq);
        String str[] = pq.toArray(new String[0]);
        Arrays.sort(str);
        for(String str1:str){
            System.out.println(str1);
        }

产生输出：

polledbingo
[bro, hepqo, first, okay, ssup, wassup, last]
bro
first
hepqo
last
okay
ssup
wassup

即使我将它转换为数组，顺序也会丢失。
我感觉这甚至不是字符串的自然排序。
有没有办法维护优先队列的插入顺序？
它们基于什么排序？

- Sachin Verma

---

请仔细阅读JavaDocs：“在方法iterator()中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。”http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html - Matt Ball

PriorityQueue 中提供排序的唯一方法是 poll() 和 peek()，而您都没有使用它们。在我看来，您想要的是一个 FIFO 队列，根本不需要 PriorityQueue。 - user207421

迭代器不保证顺序，自然排序无效，这意味着没有办法维护顺序？ - Sachin Verma

FIFO队列：LinkedList或ArrayDeque。 - Louis Wasserman

poll()和peek()根据类的Comparable.compareTo()实现或您提供的Comparator维护排序。这些都在Javadoc中有说明。您已经阅读过了吗？ - user207421

Answer 1

队列按照字符串的词典序进行排序，这是它们自然的顺序（例如'b'在'f'之前，'f'在'h'之前等）。如果您希望队列保持插入顺序，请使用普通的 Queue 而不是 PriorityQueue。

- Zim-Zam O'Pootertoot

---

在我的输出中，为什么last在wassup之后？ - Sachin Verma

@Sachin Verma，从toArray输出的元素没有特定的顺序 - 只有poll，iterator等保证遵守队列的顺序。 - Zim-Zam O'Pootertoot

不可以。请看Javadoc：“在iterator()方法中提供的Iterator不能保证以任何特定顺序遍历优先队列的元素。” 只有通过peek()和poll()方法才能提供排序。 - user207421

你是怎么知道这个的（“队列按照字符串的词典顺序排序，这是它们的自然顺序”）？有官方参考资料吗？ - FullStackDeveloper

Answer 2

Java中的优先队列是所谓堆（一种抽象数据结构）的实现。如果您查看堆数据结构，您会发现其中没有严格的键排序原则（或者用Java术语来说，集合元素）。堆ADT主要用于快速插入/删除和O(K)时间检索第一个元素（在堆的情况下将是根）。因此，请勿在Java中使用PriorityQueue数据结构搜索所有元素、排序元素或遍历元素。因为它不是为这些目的而设计的。Javadoc清楚地指出，从Collection和Iterable接口中提供的可选实现不是可以依赖的内容（即，Iterator返回的实现不能保证顺序，而Collection方法如remove()、contains()需要线性时间）。

- Sai Dubbaka

---

当然有“严格原则”。否则它就行不通了。这个“严格原则”是 A[i] <= A[i*2] <= A[i*2+1]。你当然可以用它来进行排序。Iterator 方法 hasNext() 和 next() 不是可选的。这里太容易混淆了。 - user207421