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

  |  

摘要: heapq 中维护大顶堆

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


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

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

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

1
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
2
3
1 <= piles.length <= 1e5
1 <= piles[i] <= 1e4
1 <= k <= 1e5

题解

算法:贪心

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

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

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

代码 (Python)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

Share