Python heapq最小堆异常：大值元素前置问题排查与解决

问题现象 #

在解决雇佣工人最小成本问题时，用Python的heapq模块构建最小堆：先计算每个工人的(wage/quality, quality)比率列表，再用heapq.heapify()堆化列表。但堆化后的输出里，5.101694915254237排在3.875之前，而用sort()排序能得到正确的升序顺序。

用户代码：

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        ratio = [(w / q, q) for w, q in zip(wage, quality)]
        # heapq.heappush(ratio,[(w/q,q) for w,q in zip(wage,quality)])
        heapq.heapify(ratio)
        print(ratio)

堆化后输出：

[(2.269662921348315, 89), (3.223684210526316, 76), (5.101694915254237, 59), (3.875, 56), (7.538461538461538, 39), (17.115384615384617, 26), (5.5, 86), (6.428571428571429, 14), (138.33333333333334, 3), (13.527777777777779, 36)]

原因分析 #

你误解了heapq.heapify()的作用：它构建的是最小堆结构，不是全局有序的列表。

最小堆是一种完全二叉树，核心特性是每个父节点的值都小于等于它的子节点，但不要求兄弟节点之间的顺序，也不要求整个列表按升序排列。所以堆化后的列表只是满足堆的结构规则，不是严格的有序序列：

• 列表第一个元素（堆的根节点）一定是最小值（这里2.26966...符合）；
• 索引i的节点，其子节点是2i+1和2i+2，只要父节点值≤子节点值就符合堆要求。比如索引2的5.10169...是索引0的子节点，它比根节点大，符合规则；索引3的3.875是索引1的子节点，比索引1的3.22368...大，也符合规则——兄弟节点之间不需要有序，所以出现5.10169...在3.875前面的情况是正常的。

解决方法 #

如果需要得到升序的序列，有两种方式：

1. 直接排序：如果不需要利用堆的动态维护特性，直接用sorted()对比率列表排序，得到全局有序的结果：

   ratio_sorted = sorted(ratio, key=lambda x: x[0])
   

2. 通过堆弹出获取有序序列：如果需要利用堆的特性（比如动态维护前k个最小元素），可以通过heapq.heappop()逐个弹出堆顶元素，每次弹出的都是当前堆的最小值，拼接起来就是有序序列：

   sorted_ratio = []
   while ratio:
       sorted_ratio.append(heapq.heappop(ratio))
   print(sorted_ratio)
   

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