PriorityQueue.addAll未遵循Comparator？输出顺序不符问题咨询

你遇到的问题和addAll方法无关，核心是PriorityQueue的toString()不会返回完全排序的集合，它的内部存储结构是最小堆，不是有序列表。

关键原因：堆的结构特性 #

PriorityQueue实现的是最小堆，它只保证堆顶（第一个元素）是整个集合中的最小值，而堆的内部数组不需要完全有序。只要满足每个父节点的值小于等于子节点即可：

• 你的例子中，堆的结构是根节点2，左子节点4，右子节点3，6是4的子节点。这个结构完全符合最小堆的规则（2<4、2<3、4<6），所以内部数组的顺序就是[2,4,3,6]，toString()直接输出了这个数组的原始顺序。

addAll方法没有问题 #

addAll和add方法的逻辑一致，都会正确维护堆的结构，你的代码中添加元素的方式完全正确。

如何得到预期的有序输出 #

如果需要按从小到大的顺序输出元素，需要通过poll()方法逐个取出堆顶元素（每次poll都会重新调整堆，保证下一个元素是当前最小值）：

public static void main(String[] args) {
    int[] pipes = {4, 3, 2, 6 };
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 默认就是最小堆，无需自定义Comparator
    minHeap.addAll(IntStream.of(pipes).boxed().collect(Collectors.toList()));
    // 逐个取出元素得到有序结果
    while (!minHeap.isEmpty()) {
        System.out.print(minHeap.poll() + " ");
    }
}

执行这段代码会输出2 3 4 6，符合你的预期。

补充说明 #

你自定义的Comparatoro1-o2是正确的最小堆逻辑，不过PriorityQueue默认的构造器就是实现最小堆，所以可以省略这个Comparator，代码会更简洁。

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