Heap 合集

前言

使用语言 Python, 只针对 LC Medium 和 Hard 题, 面向面试刷题
Note: 除非你面前端 (加上 JS) , 否则统一使用 Python 进行刷题

---

知识点

• Python 的 heapq 是 MinHeap（最小堆）
• 堆顶（最小值）在 heap[0]
• 没有内置 MaxHeap，要用负数 trick

基本操作

import heapq

# 创建 heap
heap = []
heapq.heapify(nums)  # 把现有 list 变成 heap，O(n)

# 插入
heapq.heappush(heap, item)  # O(log n)

# 弹出最小值
heapq.heappop(heap)  # O(log n)

# 查看最小值（不弹出）
heap[0]

# 弹出最小 + 插入新值（一步完成）
heapq.heapreplace(heap, new_item)  # O(log n)

# 插入新值 + 弹出最小（先 push 再 pop）
heapq.heappushpop(heap, new_item)  # O(log n)

MaxHeap 技巧

# 存负数
heapq.heappush(heap, -num)

# 取出时再取负
val = -heapq.heappop(heap)

带优先级的元素（tuple）

# (priority, value)，按第一个元素排序
heapq.heappush(heap, (3, "apple"))
heapq.heappush(heap, (1, "banana"))
heapq.heappush(heap, (2, "cherry"))

heapq.heappop(heap)  # (1, "banana")

---

题目

LC 347

• 347 (Top K Frequent Elements)

LC 215

• 215 (Kth Largest Element in an Array)

LC 451

• 451 (Sort Characters By Frequency)

LC 23

• 23 (Merge K Sorted List)

# 如果 val 相同，Python 会比较 node，ListNode 不能比较会报错
heappush(heap, (val, node))  # 错误

# 加个唯一的 tie-breaker
heappush(heap, (val, index, node))  # 正确

LC 253

• 253 (Meeting Rooms II)

记住如果当前的 start 和前一个 end 是一样的也得要两个 room

LC 295

• 295 (Find Median from Data Stream)

两个 heap (small, large), 保持 small 可以最多比 large 多一个, small 是类似 [-3, -2, -1], lareg 是类似 [4, 5], 所以 median 就是 - (-3)

LC 378

• 378 (Kth Smallest Element in a Sorted Matrix)

利用矩阵行列递增性质 (每次只 push 右边或下面的一个, 先右再下, 不要同时 push 两个)，用最小堆维护当前最小边界，每次 pop 得到下一个最小值，第 k 次 pop 即答案

矩阵：
1   5   9
10  11  13
12  13  15

堆 pop 顺序：
1   -> 第 1 小
5   -> 第 2 小
9   -> 第 3 小
10  -> 第 4 小
11  -> 第 5 小   <-- k = 5

LC 2402

• 2402 (Meeting Rooms III)

这题比较复杂, 要维护 2 个 Heap, busy_rooms 和 free_rooms, 会议来了 → 先把已经结束的房间还回来 → 有空房就用编号最小的 → 没空房就等“最早空出来的房间”，把会议顺延 → 最后统计哪个房间被用最多。