Java中遍历PriorityQueue使用iterator是最优方式吗？

首先纠正两个认知偏差：

1. 不存在O(1)时间遍历完n个元素的集合操作，只要需要访问全部元素，遍历的基础时间开销至少是O(n)。
2. 你提到的两种遍历方式的特性和复杂度如下：

• iterator()方式：
  总时间复杂度为O(n)，属于纯读操作，不会修改队列的底层结构。但要特别注意：PriorityQueue底层是数组实现的堆结构，迭代器直接按底层数组的存储顺序遍历，不保证返回元素的顺序符合优先级排序规则。
  实现代码：

  Iterator<MyObject> itr = queue.iterator();
  while(itr.hasNext()){
    MyObject element = itr.next();
    // 业务处理逻辑
  }
  

• 循环poll()方式：
  每次调用poll()会取出堆顶元素，之后需要调整堆结构维持堆性质，单次poll时间复杂度O(logn)，遍历完全部n个元素总时间复杂度为O(nlogn)，遍历过程会逐个清空队列。这种方式返回的元素是严格按照优先级顺序排列的。
  实现代码：

  while(!queue.isEmpty()){
    MyObject element = queue.poll();
    // 业务处理逻辑
  }
  

方案选择建议 #

如果你遍历过程不需要按优先级顺序处理元素，且遍历完成后不再使用该队列，直接选iterator()遍历就是最优方案，性能比循环poll高一个量级。
如果你必须按优先级顺序处理元素，不管后续是否保留队列，都只能选择循环poll的方式，没有复杂度更低的实现。

内容的提问来源于stack exchange，提问作者waynewingorc