在Java中对优先级队列进行排序

Question

我试图插入整数PriorityQueue,我知道:

如果在PriorityQueue构造a时未指定比较器,则使用存储在队列中的数据类型的默认比较器.默认比较器将按升序对队列进行排序

但是,我得到的输出不是按排序顺序.运行以下代码后的输出是:[2, 4, 8, 6]

public static void main(String args[]) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
    q.offer(4);
    q.offer(2);
    q.offer(8);
    q.offer(6);

    System.out.print(q);
}

有人可以解释一下原因吗？

Answer 1

一个PriorityQueue的是所谓的二元堆.它只是在第一个元素最少的意义上排序/排序.换句话说,它只关心队列前面的内容,其余部分在需要时"排序".

元素仅在它们出列时排序,即使用从队列中删除poll().这就是为什么PriorityQueue能够获得如此优异的性能的原因,因为它不会在任何时候进行任何排序.

如果你想知道堆是如何工作的,我推荐麻省理工学院关于堆的讲座.

Answer 2

当你打电话System.out.print()给你时PriorityQueue,它不是poll()你的元素,而是打电话toString().PriorityQueue没有实现toString(),所以它是toString()从AbstractCollection将被称为:

public String toString() {
    Iterator<E> i = iterator();
if (! i.hasNext())
    return "[]";

StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
    E e = i.next();
    sb.append(e == this ? "(this Collection)" : e);
    if (! i.hasNext())
    return sb.append(']').toString();
    sb.append(", ");
}
}

如您所见,此方法仅迭代PriorityQueue.正如您在PriorityQueuejavadoc中看到的:

方法iterator()中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素.如果需要有序遍历,请考虑使用Arrays.sort(pq.toArray()).

如果你想使用PriorityQueue它的意图,你需要poll()每个值并打印它:

while (!q.isEmpty()) {
    Integer i = q.poll();
    System.out.println(i);
}

输出:

2
4
6
8