Python中heapq._heapify_max函数异常求助（LeetCode 1962）

你遇到的问题核心是heapq模块的最大堆函数和普通最小堆操作不兼容：

• heapq._heapify_max(piles)会把列表转换成最大堆结构，但heapq模块的heappush是专门为最小堆设计的，它会按照最小堆的插入规则放置新元素，直接破坏了原本的最大堆结构。
• 前两次用_heappop_max能拿到最大值，是因为堆结构还没被彻底打乱；但每次用heappush插入新元素后，最大堆的父子节点关系被破坏，后续堆已经不是合法的最大堆，自然无法正确弹出最大值。

有两种可靠的解决方式：

方式一：用负数模拟最大堆（官方推荐写法） #

heapq默认只支持最小堆，我们可以把所有元素取负数存入堆，这样弹出最小的负数等价于原数的最大值，插入时也存入负数：

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        # 转换为负数，模拟最大堆
        heap = [-x for x in piles]
        heapq.heapify(heap)
        for _ in range(k):
            x = -heapq.heappop(heap)  # 弹出原数的最大值
            new_x = x - x // 2  # 等价于x//2或x//2+1，简化计算
            heapq.heappush(heap, -new_x)
        return -sum(heap)

方式二：手动维护最大堆（不推荐，依赖私有函数） #

如果一定要用最大堆，插入新元素后需要手动调用私有函数修正堆结构——因为heapq没有公开的最大堆插入函数：

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        heapq._heapify_max(piles)
        for _ in range(k):
            x = heapq._heappop_max(piles)
            new_x = x - x // 2
            heapq.heappush(piles, new_x)
            # 手动调整为最大堆结构
            heapq._siftdown_max(piles, 0, len(piles)-1)
        return sum(piles)

注意：开头带下划线的私有函数可能在Python版本更新中变更，生产环境不建议使用。

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