java - 元素的优先级队列排序

Question

为什么优先级队列的元素默认按照自然顺序排序，因为它没有实现可比较的接口(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]。为什么？应该是自然排序吧？

Answer 1

其实是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