小强的开发笔记
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 循环遍历优先队列不改变原有优先队列，也就不能保证遍历顺序是有序的。这两个顺序不一样！