元素的优先队列排序

Question

元素的优先队列排序

javascjp

13

为什么优先队列的元素默认按照自然顺序排序，即使它没有实现Comparable接口？

从文档中可以看到，元素是根据自然顺序进行排序的，但我找不到任何关于equals方法或comparable的说明。它是如何在内部实现的？

所有已实现的接口：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]。为什么会这样呢？应该是自然排序，对吧？

- kittu

源代码在src.zip中。 - Kayaman

1

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/PriorityQueue.java#587 - Thomas Jungblut

@JB Nizet：已实现的所有接口： Serializable，Iterable<E>，Collection<E>，Queue<E> - kittu

1

@JBNizet 这就是它实现的全部内容。我可以看到它说自然排序，但如果你看到这个：所有已实现的接口：Serializable、Iterable<E>、Collection<E>、Queue<E>，它并没有实现Comparable。 - kittu

2

E 需要实现 Comparable 或者定义一个 Comparator，文档中已经明确说明了这一点。为什么 PriorityQueue 需要实现 Comparable？ - Thomas Jungblut

2

@JBNizet 你可能错过了 http://stackoverflow.com/tour 的这一部分：“记住：我们都在这里学习，所以要友善和乐于助人！”尽管你的回答很有帮助，但可以更友好些。 - jaypi

4个回答

8

您看到这个顺序是因为：

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

- Saathvik

1

优先队列依靠以下内容来排序元素：

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

- Hussein Zawawi

0

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

整数和字符串值是允许在比较器中的，因为它们实现了Comparable接口。例如： public final class String implements java.io.Serializable, Comparable, CharSequence

public final class Integer extends Number implements Comparable

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

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

- SAURAV AGGARWAL

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 卢声远 Shengyuan Lu · Accepted Answer

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

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

此外，元素要么是Comparable，要么提供了Comparator。不幸的是，非可比较性检查在运行时进行，而不是编译时。一旦添加第二个元素，ClassCastException就会发生。

此外：我回答“为什么[1, 3, 2, 4]而不是打印[1, 2, 3, 4]”？

正如我之前所提到的，它不是有序的，而是专注于头部q [0]是最小值。你可以将[1、3、2、4]看作是一棵非线性的树：

1
| \
3  2
|
4