0%

Java 遍历 PriorityQueue 注意事项

最近写 LeetCode 踩了个坑,记录一下。

对于 PriorityQueue 和 ArrayList:

1
2
PriorityQueue<Integer> queue;
ArrayList<Integer> list;

下面两个操作是等价的:

1
2
3
4
5
// #1
for (Integer i: list)
queue.add(i);
// #2
queue.addAll(list);

然而下面代码中,前两个操作与第三个操作是不等价的:

1
2
3
4
5
6
7
8
// #1
for (Integer i: queue)
list.add(i);
// #2
list.addAll(i);
// #3
while (!queue.isEmpty())
list.add(queue.poll());

原因是 PriorityQueue.poll 操作会改变原有队列:弹出堆顶元素,再调整堆使其保持最小堆性质,这一改变对于维护其出列的有序性是必要的。另一方面,如果没有出列再调整这一过程,优先队列并不能保证遍历的有序性:只是简单的前序遍历。
换句话说就是 queue.poll 方法取出元素的顺序是有序的,而 addAll 方法与使用 for-each 循环遍历优先队列不改变原有优先队列,也就不能保证遍历顺序是有序的。这两个顺序不一样