在heqpq中维护大顶堆：取相反数的方式

摘要: heapq 中维护大顶堆

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在 Python 和 C++ 中与堆相关的组件中，默认都是小顶堆，类似地排序组件默认也是小的值排在前面。

在 C++ 中，如果不涉及自定义比较逻辑，仅仅是想要大顶堆，或者在排序中大的值排在前面，其实现方式差不多，都是通过 greater<int> 或 less<int> 仿函数来实现。关于这两个仿函数的描述可以参考文章 C++中对堆或优先级队列priority_queue自定义比较函数。

在 Python 中，不涉及自定义比较逻辑的情况下，大顶堆的维护与从大到小排序的实现有所区别。如果是维护从大到小的排序，可以用 reverse 这个参数实现，如下：

my_list.sort(reverse=True)

如果是维护大顶堆就麻烦一点，主要的办法是在插入或建堆的时候取相反数，然后在弹出的时候再取一次相反数即可维护原值的大顶堆的性质。

本文我们以一个使用堆的贪心算法为例，看一下在 heapq 中通过相反数的方式维护大顶堆的方法。

题目

给你一个整数数组 piles ，数组 下标从 0 开始 ，其中 piles[i] 表示第 i 堆石子中的石子数量。另给你一个整数 k ，请你执行下述操作 恰好 k 次：

• 选出任一石子堆 piles[i] ，并从中 移除 floor(piles[i] / 2) 颗石子。

注意：你可以对 同一堆 石子多次执行此操作。

返回执行 k 次操作后，剩下石子的 最小 总数。

floor(x) 为 小于 或 等于 x 的 最大 整数。（即，对 x 向下取整）。

示例 1：
输入：piles = [5,4,9], k = 2
输出：12
解释：可能的执行情景如下：

• 对第 2 堆石子执行移除操作，石子分布情况变成 [5,4,5] 。
• 对第 0 堆石子执行移除操作，石子分布情况变成 [3,4,5] 。
  剩下石子的总数为 12 。

示例 2：
输入：piles = [4,3,6,7], k = 3
输出：12
解释：可能的执行情景如下：

• 对第 2 堆石子执行移除操作，石子分布情况变成 [4,3,3,7] 。
• 对第 3 堆石子执行移除操作，石子分布情况变成 [4,3,3,4] 。
• 对第 0 堆石子执行移除操作，石子分布情况变成 [2,3,3,4] 。
  剩下石子的总数为 12 。

提示：

1 <= piles.length <= 1e5
1 <= piles[i] <= 1e4
1 <= k <= 1e5

题解

算法：贪心

每次操作选择数组中最大的数，因此可以用最大堆来维护各堆石子。

每次操作中，弹出堆顶，将其数值减去一半（下取整），将减去一半后的值再压入堆中。

操作 k 次之后，堆中所有元素之和即为答案。

代码 (Python)

相反数的方式实现大顶堆。

import heapq
import math

class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        n = len(piles)
        for i in range(n):
            piles[i] = -piles[i]
        heapq.heapify(piles)
        while k > 0:
            x = -heapq.heappop(piles)
            x -= math.floor(x / 2)
            if x > 0:
                heapq.heappush(piles, -x)
            k -= 1
        return -sum(piles)

---