堆的定义
堆 是一种特别的二叉树，满足以下条件的二叉树，可以称之为 堆：
完全二叉树；
每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。
堆 具有以下的特点：
- 可以在 O(logN)O(logN) 的时间复杂度内向 堆 中插入元素；
- 可以在 O(logN)O(logN) 的时间复杂度内向 堆 中删除元素；
- 可以在 O(1)O(1) 的时间复杂度内获取 堆 中的最大值或最小值。
堆的分类
堆 有两种类型：最大堆(大根堆) 和 最小堆(小根堆)。
最大堆：堆中每一个节点的值 都大于等于 其孩子节点的值。所以最大堆的特性是 堆顶元素（根节点）是堆中的最大值。
最小堆：堆中每一个节点的值 都小于等于 其孩子节点的值。所以最小堆的特性是 堆顶元素（根节点）是堆中的最小值。
堆的使用场景
用一句话来描述堆的使用场景就是：动态求极值。其中动态和极值两个条件缺一不可。即当我们遇到题目需要对一个数组进行持续的插入、删除，然后最终求top(N)问题时，不用想必然是堆排序问题。
Python堆模块的使用
在Python中，堆模块通过import heapq来导入，这里要说明下Python的堆都是小根堆，那么Python如何来计算大根堆呢？推荐的做法是将所有整数全部转化为负数，那么就实现了小根堆的操作。
heapq有两种方式创建堆
- 使用一个空列表，然后使用heapq.heappush()函数把值加入堆中
- 使用heap.heapify(list)转换列表成为堆结构
import heapq
# 方法1
nums = [2,5,1,7,9,10,3,4]
heap = []
for num in nums:
heapq.heappush(heap, num)
while heap:
print(heapq.heappop(heap))
# 方法2
nums = [2,5,1,7,9,10,3,4]
heapq.heapify(nums)
while heap:
print(heap.pop())
堆在日常的使用频率上不是很多，如果仅为了刷题，那么只要了解这些内容就足够做题了。当然如果想细致了解堆的构成与实现，等闲下来了专门写一篇文章来详细讲述。
力扣堆题目
堆的题目总体难度在力扣的上算是比较困难的，但是出现和面试时的频率真的很低。53道题目只有3道简单、21道困难、29道中等，今天在这里给大家推荐三道题目，掌握这三道题，这类题型就差不多了...
- 1845.座位预约管理系统 是一道简单设计题目，掌握刚才说的动态、极值，那么这道题解起来简直不要太简单
- 1046.最后一块石头的重量 是一道考察大根堆的题目，如刚才所说python中我们需要把它转化为小根堆后再进行计算
- 313.超级丑数 这道题呢，算是稍难一点的综合题目，需要我们判断堆的重复值
下来分别看看这三道题目吧：
1845.座位预约管理系统
难度：中等
题目：
请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。
请你实现 SeatManager 类：
- SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
- int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
- void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。
提示：
- 1 <= n <= 105
- 1 <= seatNumber <= n
- 每一次对reserve的调用，题目保证至少存在一个可以预约的座位。
- 每一次对unreserve的调用，题目保证seatNumber在调用函数前都是被预约状态。
- 对reserve 和unreserve的调用总共不超过105次。
示例：
示例 1：
输入：
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
输出：
[null, 1, 2, null, 2, 3, 4, 5, null]
解释：
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5 个座位。
seatManager.reserve(); // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
seatManager.reserve(); // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve(); // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.reserve(); // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
seatManager.reserve(); // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
seatManager.reserve(); // 唯一可以预约的是座位 5 ，所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。
分析
类似这种简单类设计题，在日常面试还是比较多的。
这道题我们使用小根堆，解题简直不要太简单。
解题：
import heapq
class SeatManager:
def __init__(self, n: int):
self.ret = [i for i in range(1, n + 1)]
def reserve(self):
return heapq.heappop(self.ret)
def unreserve(self, seatNumber):
heapq.heappush(self.ret, seatNumber)
1046.最后一块石头的重量
难度：简单
题目：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
分析
由于Python不支持大根堆，所以我们需要在预处理的时候，将所有数据转为负数用于适配小根堆。
循环判断的条件当然是堆内数据大于1，当为0和1时表示获取到结果，返回即可。
循环过程中，每次pop出堆内最小的两个数后，对两数根据题意进行比较：
- 若两数相等，都碾碎
- 若两数不相等，则将差值重新加入堆中
重复上面流程，最终即可获取结果。
解题：
import heapq
class Solution:
def lastStoneWeight(self, stones):
stones = [-i for i in stones]
heapq.heapify(stones)
while len(stones) > 1:
one = heapq.heappop(stones)
two = heapq.heappop(stones)
if one != two:
heapq.heappush(stones, one - two)
return -stones[0] if stones else 0
313.超级丑数
难度：中等
题目：
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
说明:
- 1 是任何给定 primes 的超级丑数。
- 给定 primes 中的数字以升序排列。
- 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
- 第 n 个超级丑数确保在 32 位有符整数范围内。
示例：
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，
前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
分析
我们可以动态维护一个当前最小的超级丑数。找到第一个，我们将其移除，再找下一个当前最小的超级丑数。
这样经过 n 轮，我们就得到了第 n 小的超级丑数。这种动态求极值的方式，符合堆排序的操作条件。
- 初始化ret = 1 为默认的返回值
- 我们通过for循环的方式每次找到一个最小值，默认为1。
- 最小值tmp出堆时，分别和primes中的每次元素p相乘后入堆。
- 此时，我们将tmp赋值给ret
- 如此反复3、4操作，直到取到第 n 个超级丑数。
在3 操作的时候，我们需要注意，由于在计算时可能存在相同值的场景，所以在出堆后，需要判断当前堆的最小值是否等于tmp，
如果等于，则需要持续出堆，一直到不相等为止。
解题：
import heapq
class Solution:
def nthSuperUglyNumber(self, n, primes):
hq = [1]
ret = 1
for i in range(n):
tmp = heapq.heappop(hq)
while hq and hq[0] == tmp:
heapq.heappop(hq)
for p in primes:
heapq.heappush(hq, p * tmp)
ret = tmp
return ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论