Kotlin PriorityQueue升序排序未按预期工作问题咨询

首先明确：Java/Kotlin的PriorityQueue是基于堆（Heap）实现的，它的内部存储数组并不保证全局有序，只保证符合堆的性质——对于小顶堆（升序Comparator），堆顶（数组第一个元素）是最小元素，每个父节点的值都小于等于其子节点；对于大顶堆（降序Comparator），堆顶是最大元素，每个父节点的值都大于等于其子节点。

你的升序案例分析 #

你编写的升序Comparator代码：

val pq = PriorityQueue<Int>(){p0,p1->
    p0-p1
}

pq.add(6)
pq.add(1)
pq.add(2)
pq.add(11)

内部存储数组是[1,6,2,11]，这完全符合小顶堆的性质：

• 堆顶元素是1（全局最小，符合升序优先级）
• 父节点1的子节点是6和2，满足1 ≤ 6、1 ≤ 2
• 父节点6的子节点是11，满足6 ≤ 11

你误以为内部应该是[1,2,6,11]这种完全升序的数组，是对PriorityQueue工作机制的误解——它不会维护全局有序数组（否则插入/删除操作的时间复杂度会大幅上升），堆结构的核心优势就是插入和取顶操作都保持O(logn)的高效性。

如果要得到升序序列，需要调用poll()方法依次取出元素：

while (!pq.isEmpty()) {
    println(pq.poll()) // 输出顺序：1 → 2 → 6 → 11
}

你的降序案例分析 #

你编写的降序Comparator代码：

val pq = PriorityQueue<Int>(){p0,p1->
    p1-p0
}

pq.add(6)
pq.add(1)
pq.add(2)
pq.add(11)

内部存储数组是[11,6,2,1]，这看起来是完全降序，但只是巧合——因为元素数量少，堆结构刚好和完全降序数组重合。如果再添加一个元素，比如pq.add(8)，内部存储会变成[11,8,2,1,6]，此时就不是完全降序了，但依然符合大顶堆的性质：

• 堆顶11是全局最大
• 11的子节点8和2，满足11 ≥ 8、11 ≥ 2
• 8的子节点6，满足8 ≥ 6

总结 #

• PriorityQueue的内部数组是堆结构，而非全局有序数组
• 只有通过poll()/peek()操作，才能获取符合优先级顺序的元素
• 升序案例的内部存储是合法的小顶堆，完全符合逻辑，你的预期错误源于对内部存储结构的误解

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