java Java中priorityQueue的顺序？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17688180/
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
Order of priorityQueue in Java?
提问by Sachin Verma
I can't understand the order of PriorityQueuein Java. As i understand they are heap based and they can not provide exact iteration order as insertion order. I want to know then on what basis priorityQueue Sort themselves.
Given code:
我无法理解PriorityQueueJava 中的顺序。据我所知，它们是基于堆的，它们不能提供准确的迭代顺序作为插入顺序。我想知道然后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);
}
produces output:
产生输出：
polledbingo
[bro, hepqo, first, okay, ssup, wassup, last]
bro
first
hepqo
last
okay
ssup
wassup
Even when i convert it to Array, the order is lost.
I can not feel this is even NATURAL ORDERING by String.
Is there any way to maintain the insertion order of priority Queues?
On what basis they sorted on?
即使我将其转换为数组，订单也会丢失。
我什至觉得这不是字符串的自然排序。
有什么办法可以保持优先队列的插入顺序吗？
他们排序的依据是什么？
采纳答案by Zim-Zam O'Pootertoot
The queue is sorting according to the strings' lexicographic order, which is their natural ordering (i.e. 'b' precedes 'f', 'f' precedes 'h', etc). If you want the queue to maintain insertion order, then use a vanilla Queueinstead of a PriorityQueue
队列根据字符串的字典顺序进行排序，这是它们的自然顺序（即“b”在“f”之前，“f”在“h”之前，等等）。如果您希望队列保持插入顺序，请使用 vanillaQueue而不是PriorityQueue
回答by Sai Dubbaka
The Priority Queues in Java are an implementation of what is called a Heap(which is an abstract data structure). If you look the Heap data structure, there is no strict principle of ordering among the keys (or collection elements in Java terms). Heap ADT is useful for mainly for fast insertion/deletion and O(K) time retrieval of the first element (which will be the root in case of the Heap). So do not use PriorityQueue data structure in Java for searching all elements, sorting elements, or traversing elements. Because it's not meant for those purposes. The javadoc clearly points out that the optionalimplementations from Collection and Iterable interfaces are not something to rely upon (i.e., Iterator returns an implementation which does not guarantee the order and the Collection methods like remove(), contains() take linear time)
Java 中的优先级队列是所谓堆（一种抽象数据结构）的实现。如果您查看堆数据结构，就会发现键（或 Java 术语中的集合元素）之间没有严格的排序原则。堆 ADT 主要用于快速插入/删除和 O(K) 时间检索第一个元素（在堆的情况下将是根）。所以不要使用Java中的PriorityQueue数据结构来搜索所有元素、排序元素或遍历元素。因为它不是为了这些目的。javadoc 清楚地指出可选的Collection 和 Iterable 接口的实现不是可依赖的（即，Iterator 返回一个不保证顺序的实现，而像 remove()、contains() 这样的 Collection 方法需要线性时间）
