堆
一句话说明
堆不是拿来“排序所有元素”的，而是拿来高效维护“当前最小值 / 最大值”的。
先记住它最重要的性质
- 最小堆：父节点永远不大于子节点
- 最大堆：父节点永远不小于子节点
所以：
- 看最小值 / 最大值：
O(1) - 插入：
O(log n) - 删除堆顶：
O(log n)
数组下标关系
如果下标从 0 开始：
parent(i) = (i - 1) / 2
left(i) = 2*i + 1
right(i) = 2*i + 2这就是为什么堆通常直接用数组实现，不需要真的建树节点。
Go 代码：手写最小堆
type MinHeap struct {
data []int
}
func (h *MinHeap) Len() int {
return len(h.data)
}
func (h *MinHeap) Peek() int {
return h.data[0]
}
func (h *MinHeap) Push(x int) {
h.data = append(h.data, x)
h.siftUp(len(h.data) - 1)
}
func (h *MinHeap) Pop() int {
n := len(h.data)
top := h.data[0]
h.data[0] = h.data[n-1]
h.data = h.data[:n-1]
if len(h.data) > 0 {
h.siftDown(0)
}
return top
}
func (h *MinHeap) siftUp(i int) {
for i > 0 {
p := (i - 1) / 2
if h.data[p] <= h.data[i] {
break
}
h.data[p], h.data[i] = h.data[i], h.data[p]
i = p
}
}
func (h *MinHeap) siftDown(i int) {
n := len(h.data)
for {
smallest := i
left := 2*i + 1
right := 2*i + 2
if left < n && h.data[left] < h.data[smallest] {
smallest = left
}
if right < n && h.data[right] < h.data[smallest] {
smallest = right
}
if smallest == i {
break
}
h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
i = smallest
}
}Go 标准库里怎么用
实际做题时，Go 一般直接用 container/heap。
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}最小堆默认这样写；如果想做最大堆，就把 Less 反过来。
上浮和下沉到底在干什么
插入后上浮
新元素先丢到数组末尾，然后一路和父节点比较：
新元素太小，就往上换
直到堆性质恢复删除堆顶后下沉
把最后一个元素拿来补到根，再一路往下和更小的孩子交换：
根太大，就往下换
直到堆性质恢复建堆为什么是 O(n)
很多人第一反应会以为是 n 次插入，所以 O(n log n)。
但真正高效的建堆是：
- 从最后一个非叶子节点开始
- 逐个向下
siftDown
func (h *MinHeap) Heapify(nums []int) {
h.data = append([]int(nil), nums...)
for i := len(h.data)/2 - 1; i >= 0; i-- {
h.siftDown(i)
}
}这个过程总复杂度是 O(n)。
经典题型
第 K 大元素
核心思路不是“建最大堆全弹出来”，而是：
- 维护一个大小为
k的最小堆 - 堆顶就是当前第
k大
func findKthLargest(nums []int, k int) int {
h := &IntHeap{}
heap.Init(h)
for _, num := range nums {
if h.Len() < k {
heap.Push(h, num)
continue
}
if num > (*h)[0] {
heap.Pop(h)
heap.Push(h, num)
}
}
return (*h)[0]
}合并 K 个有序链表
本质是：
- 堆里永远只放每条链表当前最小的候选节点
数据流中位数
本质是双堆：
- 一个最大堆维护较小一半
- 一个最小堆维护较大一半
堆和优先队列的关系
堆 = 实现优先队列的一种经典方式题目里说“优先队列”，你脑子里通常就该先想到堆。
什么时候该想到堆
- 反复取最小值 / 最大值
- 动态维护 Top K
- 多路归并
- 带权图最短路 / 最小生成树
- 实时调度
易错点
- 堆不是完全有序结构，只保证堆顶最优。
- 想查任意元素是否存在，堆并不擅长。
container/heap里Pop和Push操作的是切片末尾，真正的堆调整由标准库调用。- 写最大堆时别忘了把比较函数反过来。