java 元素的优先队列排序

Priority queue ordering of elements

提问by kittu

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

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

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?

从docs，它说元素是基于自然顺序排序的，但我找不到任何关于 equals 方法或可比方法的地方。内部如何发生？

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

所有实现的接口：Serializable、Iterable、Collection、Queue。

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

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

Example:

例子：

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

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

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

回答by u290629

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

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

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

PriorityQueue不需要排序，相反，它专注于数据头。插入时间为O(log n)。排序浪费时间，对队列毫无用处。

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

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

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

PLUS：我对为什么 [1, 3, 2, 4] 而不是打印 [1, 2, 3, 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:

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

1
| \
3  2
|
4

回答by Saathvik

You are seeing that order because:

1. Internally System.out.println() will be invoking the toString() method which in turn uses the iterator to iterate through the elements of the queue. But the iterator does not guarantee any specific order to traverse the elements. Refer this

您看到该顺序是因为：

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

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

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

2. Priority queue is based on priority heap. When an element is inserted without any comparator then priority queue uses siftUpComparable() method internally. siftUpComparable() compares the current element with the element at it's parent position in the heap. If the order is not correct then current element and parent element are swapped. This is done until the current element and parent element are in correct order. Ordering is based on natural order of the element.

3. Since priority queue is based on priority heap its main focus will be on element in front of the queue. So the elements are ordered when an element is dequeued from the queue using poll(). This is done to increase the performance of Priority queue. Priority queue only orders the elements when it requires.
If you want to see the order as [1, 2, 3, 4] then use this

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

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

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

回答by Hussein Zawawi

The priority queue relies on the following to order the elements:

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

• Element must be a Comparable type
• Need to provide Comparator implementation for the queue

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

回答by SAURAV AGGARWAL

Actually PriorityQueue allows only those elements which implements Comparable or you need to provide Custom Comparator.

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

Integer and String values are allowed in Comparator because they implement Comparable interface. e.g. public final class String implements java.io.Serializable, Comparable, CharSequence

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

public final class Integer extends Number implements Comparable

public final class Integer extends Number实现Comparable

If you create your own class e.g Employee then it should implement Comparable or you should provide your custom Comparator.

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

I hope this will resolve your queries!!!!

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