元素的优先队列排序 [英] Priority queue ordering of elements

问题描述

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

How come the elements of priority queue are ordered according to natural order by default as it doesn't implement comparable interface.

在 docs 中，它说元素是根据自然顺序进行排序的，但是我在任何地方都找不到关于equals方法或可比性的信息.它在内部如何发生?

From the docs, it says elements are ordered based on natural ordering but I can't find anywhere it talks about equals method nor comparable. Hows it happening internally?

所有已实现的接口:可序列化，可迭代，集合，队列.

All Implemented Interfaces: Serializable, Iterable, Collection, Queue.

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

If it implements comparable then why doesn't it say in the above line

示例:

    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].为什么?应该自然排序吧?

Also third print statement prints [1, 3, 2, 4] instead of prints [1, 2, 3, 4]. Why? It should be natural ordering right?

推荐答案

实际上PriorityQueue的内部数据结构没有排序，它是

Actually internal data structure of PriorityQueue is not ordered, it is a heap.

PriorityQueue无需排序，它专注于数据的 head .插入时间为 O(log n).排序浪费了时间，对队列毫无用处.

PriorityQueue doesn't need to be ordered, instead, it focuses on head of data. Insertion is in O(log n) time. Sorting wastes time and useless for a queue.

此外，提供了元素-a Comparable或Comparator.不幸的是，不可比的检查是在运行时而不是编译时进行的.添加第二个元素后，就会出现ClassCastException.

Moreover, either the element is-a Comparable, or a Comparator is provided. Unfortunately, non-comparable checking is at runtime, rather than compile time. Once second element is added, ClassCastException occurs.

PLUS:我对为什么用[1、3、2、4]而不是[1、2、3、4] 的答案?

PLUS: My answer to why [1, 3, 2, 4] instead of prints [1, 2, 3, 4]?

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

As I mentioned before, it's not ordered, instead it focuses on head q[0] is minimum, that's it. You could see the [1, 3, 2, 4] as a tree which is NOT linear:

1
| \
3  2
|
4

这篇关于元素的优先队列排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！