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

java priority-queue

2022-09-01 19:59:20

我试图在中插入整数，我知道：PriorityQueue

如果在构造优先级队列时未指定比较器，则使用队列中存储的数据类型的默认比较器。默认比较器将按升序对队列进行排序

但是，我获得的输出不是按排序顺序排列的。运行以下代码后的输出是：[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);
}

有人可以解释为什么吗？

答案 1

优先级队列就是所谓的二进制堆。它仅在第一个元素最少的意义上进行排序/排序。换句话说，它只关心队列前面的内容，其余的在需要的时候是“订购”的。

元素仅在排队时排序，即使用从队列中删除。这就是优先级队列设法具有如此好性能的原因，因为它在任何时候都不会执行任何超出其需要的排序。poll()

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

答案 2

当您调用您的时，它不会从中调用您的元素，而是调用。不实现，因此它将从中调用：System.out.print()PriorityQueuepoll()toString()PriorityQueuetoString()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 javadoc中看到的：PriorityQueue

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

如果要使用，则必须对每个值进行打印：PriorityQueuepoll()

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

输出：