元素的优先级队列排序

Question

为什么优先级队列的元素默认按照自然顺序排序，因为它没有实现可比较的接口。

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

第三个打印语句打印 [1, 3, 2, 4] 而不是打印 [1, 2, 3, 4]。为什么？应该是自然顺序吧？

Answer 1

其实PriorityQueue的内部数据结构是无序的，是heap。

PriorityQueue不需要排序，而是关注head的数据。插入需要 O(log n) 时间。排序浪费时间，对队列没用。

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

PLUS：我对 为什么 [1, 3, 2, 4] 而不是打印 [1, 2, 3, 4]?

的回答

正如我之前提到的，它没有顺序，而是专注于头部 q[0] 是最小的，就是这样。您可以将 [1, 3, 2, 4] 视为一棵非线性树：

1
| \
3  2
|
4

Answer 2

优先级队列依赖于以下元素排序：

元素必须是 Comparable 类型
需要为队列提供比较器实现

Answer 3

实际上 PriorityQueue 只允许那些实现 Comparable 的元素，或者您需要提供 Custom Comparator。

Comparator 中允许使用整数和字符串值，因为它们实现了 Comparable 接口。例如 public final class String implements java.io.Serializable, Comparable, CharSequence

public final class Integer extends Number implements Comparable

如果您创建自己的 class 例如 Employee，那么它应该实现 Comparable 或者您应该提供您的自定义 Comparator。

希望这能解决您的疑问！！！！

Answer 4

您看到该订单是因为：

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());
}

元素的优先级队列排序

Priority queue ordering of elements

java

scjp