元素的优先级队列排序

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

无需订购。相反，它专注于数据的head。插入需要 O(log n) 时间。排序浪费时间，而且对于队列来说毫无用处。

此外，该元素或者是-

Comparable

，或者提供了

Comparator

。不幸的是，不可比较的检查是在运行时，而不是编译时。添加第二个元素后，就会出现

ClassCastException

。

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

正如我之前提到的，它不是订购的。相反，它专注于头部

q[0]

是最小的；就是这样。 你可以将 [1, 3, 2, 4] 视为一棵不是线性的树：

1
| \
3  2
|
4

Answer 2

您看到该订单是因为：

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 3

优先级队列依赖以下元素对元素进行排序：

• 元素必须是可比较类型
• 需要为队列提供Comparator实现

Answer 4

实际上 PriorityQueue 只允许那些实现 Comparable 的元素，否则你需要提供自定义比较器。

Comparator 中允许使用整数和字符串值，因为它们实现了 Comparable 接口。例如 公共最终类 String 实现 java.io.Serialized、Comparable、CharSequence

公共最终类 Integer 扩展 Number 实现 Comparable

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

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