4

可能重复：
为什么这个奇怪的顺序发生在 java 的 PriorityQueue 中？

请看下面的代码：

public static void main(String[] args) {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    Iterator<String> i = q.iterator();
    while(i.hasNext())
        System.out.print(i.next() + " ");
}

有人可以解释一下为什么输出是

airplane car bicycle

代替

airplane bicycle car

?

因为在 API 中它说优先级队列的元素是根据它们的自然顺序排序的。

4

2 回答 2

9

根据迭代器的javadoc：

迭代器不会以任何特定顺序返回元素。

但是，第一项（头部）保证是最小的。所以这应该打印你所期望的：

public static void main(String[] args) throws Exception {
    Queue<String> q = new PriorityQueue<String>();
    q.offer("car");
    q.offer("airplane");
    q.offer("bicycle");
    String e = null;
    while ((e = q.poll()) != null) {
        System.out.println(e);
    }
}

如果要对迭代进行排序，则需要使用不同的结构，例如，TreeSet如果没有重复项，则为 a。

于 2012-12-02T11:13:42.930 回答
2

PriorityQueue 基于优先级堆。尽管元素没有排序，但这种数据结构允许非常快速地检索最少元素。向 PriorityQueue 添加元素比向基于树的 TreeSet 添加元素要快。由于元素未排序，因此正如 API 所说，迭代器“不会以任何特定顺序返回元素”。

于 2012-12-02T12:48:23.553 回答