元素的优先级队列排序

Question

为什么优先级队列的元素默认按照自然顺序排序,因为它没有实现类似的接口.

从文档中,它说元素是基于自然顺序排序的,但我找不到任何关于equals方法或类似的方法.它内部发生了什么？

所有已实现的接口:Serializable,Iterable,Collection,Queue.

如果它实现了可比性,那么为什么它不能在上面的行中说出来

例:

    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

您看到这个顺序是因为：

1. System.out.println() 在内部将调用 toString() 方法，该方法又使用迭代器来迭代队列的元素。但迭代器不保证遍历元素的任何特定顺序。参考这个

http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

2.优先级队列是基于优先级堆的。当在没有任何比较器的情况下插入元素时，优先级队列在内部使用 siftUpComparable() 方法。siftUpComparable() 将当前元素与堆中其父位置的元素进行比较。如果顺序不正确，则交换当前元素和父元素。这样做直到当前元素和父元素的顺序正确为止。排序基于元素的自然顺序。

3. 由于优先级队列基于优先级堆，因此它的主要关注点将是队列前面的元素。因此，当使用 poll() 将元素从队列中出队时，元素就会被排序。这样做是为了提高优先级队列的性能。优先级队列仅在需要时对元素进行排序。
如果您想将顺序视为 [1, 2, 3, 4]，请使用此

while(pq.size() != 0) { 
    System.out.println(pq.poll());
}

Answer 2

实际上内部数据结构PriorityQueue不是有序的,它是一堆.

PriorityQueue不需要订购,而是专注于数据的头部.插入时间为O(log n).排序浪费时间并且对队列无用.

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

加:我回答为什么[ 1,3,2,4 ]而不是打印[1,2,3,4]？

正如我之前提到的,它不是有序的,而是专注于头部q[0]是最小的,就是这样.您可以将[1,3,2,4]视为不是线性的树:

1
| \
3  2
|
4