队列未自然排序

Question

请看下面的代码：

可能重复：
为什么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中指出优先队列的元素是按照它们的自然顺序排序的。

- user1870178

---

刚刚发现这个：为什么Java中PriorityQueue会出现奇怪的顺序？ - assylias

Answer 1

根据迭代器的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。

- assylias

---

@Lang 这可能不是随机的 - 我没有查看实现，但当您插入新项时可能发生的情况是，如果它比头部小，则首先插入，否则将其放在尾部。这可以解释您所看到的顺序。 - assylias

但为什么我总是得到相同的随机顺序？迭代器似乎有问题。 - user1870178

很抱歉，我的问题是在你回答之后才出现的。 - user1870178

Answer 2

PriorityQueue是基于优先级堆的数据结构。尽管元素没有排序，但这种数据结构允许快速检索最小元素。相比基于树的TreeSet，向PriorityQueue中添加元素更快。由于元素没有排序，因此迭代器不会按照特定顺序返回元素，正如API所说。

- Evgeniy Dorofeev