最近写 LeetCode 踩了个坑,记录一下。
对于 PriorityQueue 和 ArrayList:
1 | PriorityQueue<Integer> queue; |
下面两个操作是等价的:
1 | // #1 |
然而下面代码中,前两个操作与第三个操作是不等价的:
1 | // #1 |
原因是 PriorityQueue.poll
操作会改变原有队列:弹出堆顶元素,再调整堆使其保持最小堆性质,这一改变对于维护其出列的有序性是必要的。另一方面,如果没有出列再调整这一过程,优先队列并不能保证遍历的有序性:只是简单的前序遍历。
换句话说就是 queue.poll
方法取出元素的顺序是有序的,而 addAll
方法与使用 for-each 循环遍历优先队列不改变原有优先队列,也就不能保证遍历顺序是有序的。这两个顺序不一样!