元素的优先队列排序

Question

默认情况下，优先级队列的元素如何按照自然顺序排序，因为它没有实现可比的接口。

从文档中可以看出，元素是根据自然顺序进行排序的，但是我找不到任何关于equals方法或可比性的东西。它在内部如何发生？

所有实现的接口：可序列化，可迭代，集合，队列。

如果它实现可比性，那么为什么不在上一行说

例：

    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]
    }
}

第三条打印语句也将打印[1、3、2、4]，而不是打印[1、2、3、4]。为什么？应该自然排序吧？

Answer 1

其实内部的数据结构PriorityQueue不是有序的，它是一个
堆 。

PriorityQueue不需要排序，而是专注于数据 头 。插入时间为 O（log n） 。排序浪费时间，对队列毫无用处。

此外，提供元素is -a Comparable或a Comparator。不幸的是，不可比较的检查是在 运行
时而不是编译时进行的。一旦添加第二个元素，ClassCastException就会发生。

加：我对 为什么[ 1、3、2、4 ]而不打印[1、2、3、4]的 回答？

正如我之前提到的，它不是有序的，而是集中在q[0]最小的头部上，仅此而已。您可能会看到[1、3、2、4]是一棵不是线性的树：

1
| \
3  2
|
4