为什么优先级队列的元素默认按照自然顺序排序,因为它没有实现可比较的接口(interface)。
来自docs ,它说元素是根据自然顺序排序的,但我找不到它谈论 equals 方法或可比方法的任何地方。内部情况如何?
All Implemented Interfaces: Serializable, Iterable, Collection, Queue.
如果它实现了 comparable 那么为什么上面一行没有说明
例子:
public static void main(String[] args) {
PriorityQueue<String> pq = new PriorityQueue<String>();
pq.add("2");
pq.add("4");
System.out.println(pq); //prints [2, 4]
pq.offer("1");
System.out.println(pq); // prints [1, 4, 2]
pq.add("3");
System.out.println(pq); // prints [1, 3, 2, 4]
}
}
第三个 print 语句也打印 [1, 3, 2, 4] 而不是 [1, 2, 3, 4]。为什么?应该是自然排序吧?
最佳答案
其实是PriorityQueue
的内部数据结构未排序,它是一个 heap 强>。
PriorityQueue
不需要排序,而是专注于数据的 head。插入时间为 O(log n)。排序浪费时间,对队列毫无用处。
此外,元素是-a Comparable
, 或 Comparator
提供。不幸的是,不可比较的检查是在运行时,而不是编译时。添加第二个元素后,ClassCastException
发生。
另外:我对为什么 [1, 3, 2, 4] 而不是打印 [1, 2, 3, 4] 的回答?
正如我之前提到的,它没有排序,而是专注于头部 q[0]
是最小的,仅此而已。
您可以将 [1, 3, 2, 4] 视为非线性树:
1
| \
3 2
|
4
关于java - 元素的优先级队列排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30072077/