Python中heapq.heappush处理元组未按预期工作的问题咨询

你观察到的现象完全正确，问题的核心在于：heapq维护的是二叉最小堆结构，而非完全排序的数组。

什么是最小堆？ #

最小堆是一种二叉树结构，它的核心特性是：每个父节点的值都小于等于它的子节点值。堆在数组中的存储只是这种树结构的扁平化表现，并不是按顺序排列的列表。

验证你得到的堆结构 #

看你最终得到的arr：

[(-9, 333), (-8, 505), (-6, 2), (-7, 94), (-2, 3), (-3, 101), (-4, 13), (-1, 5), (-5, 10)]

我们逐个检查父节点和子节点的关系（数组中索引i的子节点是2i+1和2i+2）：

• 根节点（索引0）(-9,333) <= 子节点索引1(-8,505)、索引2(-6,2)，符合；
• 索引1的(-8,505) <= 子节点索引3(-7,94)、索引4(-2,3)，符合；
• 索引2的(-6,2) <= 子节点索引5(-3,101)、索引6(-4,13)，符合；
• 索引3的(-7,94) <= 子节点索引7(-1,5)、索引8(-5,10)，符合；
  所有父节点都满足最小堆的要求，所以这个数组是合法的最小堆结构。

如何得到完全排序的结果 #

如果需要按元组第一个元素排序的完整列表，不能直接使用堆数组，而是要通过heapq.heappop()逐个弹出元素——每次pop都会取出当前堆的最小值（根节点），然后自动调整堆结构，保证剩下的元素依然满足堆特性。示例代码：

import heapq

inputArr = [
    (-8, 505), (-9, 333), (-6, 2), (-7, 94),
    (-2, 3), (-3, 101), (-4, 13), (-1, 5), (-5, 10)
]

arr = []
for tup in inputArr:
    heapq.heappush(arr, tup)

# 逐个弹出得到排序后的列表
sorted_arr = []
while arr:
    sorted_arr.append(heapq.heappop(arr))

print(sorted_arr)

运行后会得到完全按第一个元素升序排列的结果：

[(-9, 333), (-8, 505), (-7, 94), (-6, 2), (-5, 10), (-4, 13), (-3, 101), (-2, 3), (-1, 5)]

另外补充：如果想直接将列表转为堆，也可以用heapq.heapify(inputArr)，效率比逐个push更高，但得到的依然是堆结构数组，不是排序后的列表。

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