堆与优先队列

堆（Heap）是一种特殊的完全二叉树，它用数组就能高效表示，是优先队列的标准实现。大顶堆保证堆顶是最大值，小顶堆保证堆顶是最小值。堆在 Top K 问题、堆排序、任务调度、Dijkstra 最短路径等场景无处不在。本篇将从堆的概念讲起，覆盖上浮下沉操作、Go 标准库 container/heap 的用法、优先队列的实现，以及 Top K、合并 K 个有序链表、数据流中位数等经典问题。掌握堆，是解决「动态维护最值」类问题的钥匙。

一、堆的概念

1. 完全二叉树

堆是一棵完全二叉树：除最后一层外所有层都满，最后一层从左到右连续填充。这个性质让堆可以用数组紧凑表示，无需指针。

2. 大顶堆、小顶堆

大顶堆（Max Heap）：每个节点的值 ≥ 其子节点的值，堆顶是最大值。
小顶堆（Min Heap）：每个节点的值 ≤ 其子节点的值，堆顶是最小值。

注意堆不等于排序后的数组：堆只保证父子之间的偏序关系，兄弟之间没有顺序要求。这也是为什么堆只能 O(1) 取最值，不能 O(1) 取第 K 大。

3. 堆的数组表示

对于下标 i 的节点（从 0 开始）：

父节点：(i - 1) / 2
左孩子：2 * i + 1
右孩子：2 * i + 2

package main

import "fmt"

func main() {
	// 数组 [9, 7, 8, 5, 6] 表示的大顶堆：
	//        9
	//       / \
	//      7   8
	//     / \
	//    5   6
	heap := []int{9, 7, 8, 5, 6}
	for i := range heap {
		parent := (i - 1) / 2
		if i == 0 {
			parent = -1
		}
		left := 2*i + 1
		right := 2*i + 2
		fmt.Printf("节点 %d (值=%d) 父=%d 左=%d 右=%d\n",
			i, heap[i], parent, left, right)
	}
}

二、堆的操作

1. 上浮（sift up）

插入元素时，把它放到数组末尾，然后不断与父节点比较，不满足堆性质就交换，直到满足或到根。O(log n)。

2. 下沉（sift down）

删除堆顶时，把末尾元素移到堆顶，然后不断与较大的孩子比较交换，直到满足或到叶。O(log n)。

3. 完整堆实现

下面手写一个大顶堆，包含插入、删除堆顶、建堆：

package main

import "fmt"

type MaxHeap struct {
	data []int
}

func (h *MaxHeap) Len() int { return len(h.data) }

// 上浮
func (h *MaxHeap) siftUp(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if h.data[i] <= h.data[parent] {
			break
		}
		h.data[i], h.data[parent] = h.data[parent], h.data[i]
		i = parent
	}
}

// 下沉
func (h *MaxHeap) siftDown(i int) {
	n := len(h.data)
	for {
		left := 2*i + 1
		right := 2*i + 2
		largest := i
		if left < n && h.data[left] > h.data[largest] {
			largest = left
		}
		if right < n && h.data[right] > h.data[largest] {
			largest = right
		}
		if largest == i {
			break
		}
		h.data[i], h.data[largest] = h.data[largest], h.data[i]
		i = largest
	}
}

// 插入
func (h *MaxHeap) Push(val int) {
	h.data = append(h.data, val)
	h.siftUp(len(h.data) - 1)
}

// 删除堆顶
func (h *MaxHeap) Pop() (int, bool) {
	if len(h.data) == 0 {
		return 0, false
	}
	top := h.data[0]
	last := len(h.data) - 1
	h.data[0] = h.data[last]
	h.data = h.data[:last]
	if len(h.data) > 0 {
		h.siftDown(0)
	}
	return top, true
}

// 查看堆顶
func (h *MaxHeap) Peek() (int, bool) {
	if len(h.data) == 0 {
		return 0, false
	}
	return h.data[0], true
}

// 从数组建堆：从最后一个非叶节点开始下沉
func (h *MaxHeap) BuildHeap(arr []int) {
	h.data = append([]int(nil), arr...)
	for i := len(h.data)/2 - 1; i >= 0; i-- {
		h.siftDown(i)
	}
}

func main() {
	h := &MaxHeap{}
	h.Push(3)
	h.Push(9)
	h.Push(5)
	h.Push(1)
	h.Push(7)
	fmt.Println("堆顶:", mustPeek(h.Peek()))

	for h.Len() > 0 {
		v, _ := h.Pop()
		fmt.Printf("%d ", v)
	}
	fmt.Println()

	// 建堆
	h2 := &MaxHeap{}
	h2.BuildHeap([]int{4, 10, 3, 5, 1})
	v, _ := h2.Peek()
	fmt.Println("建堆后堆顶:", v)
}

func mustPeek(v int, ok bool) int {
	if !ok {
		return -1
	}
	return v
}

建堆的复杂度是 O(n) 而非 O(n log n)——因为大部分节点在底层，下沉距离很短，数学上可证明总和为 O(n)。

三、Go 标准库：container/heap

Go 标准库 container/heap 实现了最小堆，通过实现 heap.Interface 即可使用。

1. heap.Interface

type Interface interface {
	sort.Interface
	Push(x any)
	Pop() any
}

需要实现 Len、Less、Swap、Push、Pop 五个方法。注意 Push 和 Pop 的接收者必须是指针，因为要修改切片长度。

2. 自定义堆实现

下面实现一个小顶堆，并用它做堆排序：

package main

import (
	"container/heap"
	"fmt"
)

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
}

func main() {
	h := &IntHeap{5, 3, 8, 1, 9, 2}
	heap.Init(h) // O(n) 建堆
	fmt.Println("堆顶（最小）:", (*h)[0])

	// 不断弹出得到升序
	var sorted []int
	for h.Len() > 0 {
		sorted = append(sorted, heap.Pop(h).(int))
	}
	fmt.Println("堆排序结果:", sorted)
}

四、优先队列

优先队列（Priority Queue）是「元素带优先级、出队按优先级」的队列。堆是实现优先队列的标准方式：大顶堆对应最大优先出队，小顶堆对应最小优先出队。

1. 基于堆实现

package main

import (
	"container/heap"
	"fmt"
)

type Task struct {
	Priority int
	Name     string
}

type PriorityQueue []Task

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	// 大顶堆：优先级高的先出
	return pq[i].Priority > pq[j].Priority
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any)   { *pq = append(*pq, x.(Task)) }
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[:n-1]
	return x
}

func main() {
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Task{3, "低优先级任务"})
	heap.Push(pq, Task{1, "最低优先级任务"})
	heap.Push(pq, Task{5, "高优先级任务"})
	heap.Push(pq, Task{4, "较高优先级任务"})

	for pq.Len() > 0 {
		t := heap.Pop(pq).(Task)
		fmt.Printf("优先级 %d: %s\n", t.Priority, t.Name)
	}
}

五、常见算法

1. 堆排序

堆排序分两步：建堆 O(n)，然后不断交换堆顶与末尾、下沉 O(n log n)，总体 O(n log n)，空间 O(1)。

package main

import "fmt"

func heapSort(nums []int) {
	n := len(nums)
	// 建大顶堆
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(nums, i, n)
	}
	// 逐个把堆顶放到末尾
	for i := n - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		siftDown(nums, 0, i)
	}
}

func siftDown(nums []int, i, n int) {
	for {
		left := 2*i + 1
		right := 2*i + 2
		largest := i
		if left < n && nums[left] > nums[largest] {
			largest = left
		}
		if right < n && nums[right] > nums[largest] {
			largest = right
		}
		if largest == i {
			break
		}
		nums[i], nums[largest] = nums[largest], nums[i]
		i = largest
	}
}

func main() {
	nums := []int{3, 1, 4, 1, 5, 9, 2, 6, 5}
	heapSort(nums)
	fmt.Println("堆排序:", nums)
}

2. Top K 问题

求数组中第 K 大/前 K 大元素。两种思路：

小顶堆维护 K 个最大元素：堆大小始终保持 K，遍历完堆顶即第 K 大。O(n log K) 时间，O(K) 空间。适合 n 远大于 K 的场景（如流式数据）。
快速选择：基于快排划分，平均 O(n)，最坏 O(n²)。适合一次性查询。

package main

import (
	"container/heap"
	"fmt"
)

type MinHeap []int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// 第 K 大元素
func findKthLargest(nums []int, k int) int {
	h := &MinHeap{}
	for _, v := range nums {
		heap.Push(h, v)
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	return (*h)[0]
}

// 前 K 个最大元素
func topKFrequent(nums []int, k int) []int {
	// 先统计频率
	count := make(map[int]int)
	for _, v := range nums {
		count[v]++
	}
	// 小顶堆按频率排序
	h := &FreqHeap{}
	heap.Init(h)
	for val, freq := range count {
		heap.Push(h, Item{val, freq})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	var result []int
	for h.Len() > 0 {
		result = append(result, heap.Pop(h).(Item).val)
	}
	return result
}

type Item struct {
	val  int
	freq int
}

type FreqHeap []Item

func (h FreqHeap) Len() int            { return len(h) }
func (h FreqHeap) Less(i, j int) bool  { return h[i].freq < h[j].freq }
func (h FreqHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *FreqHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *FreqHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	fmt.Println("第 2 大:", findKthLargest(nums, 2)) // 5

	nums2 := []int{1, 1, 1, 2, 2, 3}
	fmt.Println("前 2 高频:", topKFrequent(nums2, 2)) // [2 1]
}

3. 合并 K 个有序链表（LC 23）

把 K 个有序链表合并成一个。用小顶堆每次取最小节点。

package main

import (
	"container/heap"
	"fmt"
)

type ListNode struct {
	Val  int
	Next *ListNode
}

type NodeHeap []*ListNode

func (h NodeHeap) Len() int            { return len(h) }
func (h NodeHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h NodeHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *NodeHeap) Push(x any)         { *h = append(*h, x.(*ListNode)) }
func (h *NodeHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func mergeKLists(lists []*ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	h := &NodeHeap{}
	heap.Init(h)
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}
	for h.Len() > 0 {
		node := heap.Pop(h).(*ListNode)
		cur.Next = node
		cur = cur.Next
		if node.Next != nil {
			heap.Push(h, node.Next)
		}
	}
	return dummy.Next
}

func buildList(vals []int) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for _, v := range vals {
		cur.Next = &ListNode{Val: v}
		cur = cur.Next
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("nil")
}

func main() {
	l1 := buildList([]int{1, 4, 5})
	l2 := buildList([]int{1, 3, 4})
	l3 := buildList([]int{2, 6})
	printList(mergeKLists([]*ListNode{l1, l2, l3}))
}

复杂度：N 个节点，K 个链表，每个节点入堆出堆一次 O(log K)，总 O(N log K)。

4. 数据流中位数（LC 295）

维护两个堆：大顶堆存较小的一半，小顶堆存较大的一半，两堆大小差不超过 1。中位数即两堆顶的平均或大顶堆顶。

package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap []int
type MinHeap []int

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

type MedianFinder struct {
	left  *MaxHeap // 较小的一半，堆顶是最大
	right *MinHeap // 较大的一半，堆顶是最小
}

func Constructor() MedianFinder {
	return MedianFinder{left: &MaxHeap{}, right: &MinHeap{}}
}

func (mf *MedianFinder) AddNum(num int) {
	// 先加入 left
	heap.Push(mf.left, num)
	// 把 left 堆顶移到 right，保证 left 全部 <= right
	heap.Push(mf.right, heap.Pop(mf.left))
	// 平衡大小：left 可以比 right 多 1
	if mf.right.Len() > mf.left.Len() {
		heap.Push(mf.left, heap.Pop(mf.right))
	}
}

func (mf *MedianFinder) FindMedian() float64 {
	if mf.left.Len() > mf.right.Len() {
		return float64((*mf.left)[0])
	}
	return float64((*mf.left)[0]+(*mf.right)[0]) / 2.0
}

func main() {
	mf := Constructor()
	mf.AddNum(1)
	mf.AddNum(2)
	fmt.Println("中位数:", mf.FindMedian()) // 1.5
	mf.AddNum(3)
	fmt.Println("中位数:", mf.FindMedian()) // 2
}

六、LeetCode 经典题解析

1. 数组中第 K 大元素（LC 215）

前面 findKthLargest 已实现。回顾两种思路：小顶堆 O(n log K) 适合流式数据；快速选择平均 O(n) 适合一次性查询。

2. 前 K 个高频元素（LC 347）

前面 topKFrequent 已实现：先哈希表统计频率，再用小顶堆维护 K 个高频元素。

3. 滑动窗口最大值（LC 239）

可以用大顶堆（存值和下标），出堆时检查下标是否在窗口内。但更优的是单调队列（见栈与队列篇）。这里给出堆解法：

package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	val int
	idx int
}

type MaxHeap []Item

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].val > h[j].val }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *MaxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func maxSlidingWindow(nums []int, k int) []int {
	h := &MaxHeap{}
	heap.Init(h)
	var result []int
	for i := 0; i < len(nums); i++ {
		heap.Push(h, Item{nums[i], i})
		if i >= k-1 {
			// 移除超出窗口的堆顶
			for h.Len() > 0 && (*h)[0].idx <= i-k {
				heap.Pop(h)
			}
			result = append(result, (*h)[0].val)
		}
	}
	return result
}

func main() {
	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	fmt.Println("滑动窗口最大值:", maxSlidingWindow(nums, 3))
}

七、复杂度分析

操作	时间复杂度	备注
查看堆顶	O(1)	堆的核心优势
插入	O(log n)	上浮
删除堆顶	O(log n)	下沉
建堆	O(n)	从底向上
堆排序	O(n log n)	原地排序
Top K（堆）	O(n log K)	流式友好
合并 K 链表	O(N log K)	N 总节点数

八、小结

堆是「动态维护最值」的利器，本篇要点：

堆是完全二叉树，用数组表示：父 (i-1)/2，左孩子 2i+1，右孩子 2i+2。大顶堆父≥子，小顶堆父≤子。
核心操作：上浮（插入后向上调整）、下沉（删除堆顶后向下调整），都是 O(log n)。建堆是 O(n)。
Go 标准库 container/heap 实现 heap.Interface 五个方法即可，默认小顶堆，改 Less 可变大小顶。
优先队列就是堆的应用：按优先级出队，任务调度、Dijkstra 都依赖它。
Top K 问题：小顶堆维护 K 个最大元素，O(n log K)；流式数据首选堆，一次性查询可用快速选择。
双堆技巧：数据流中位数用大顶堆 + 小顶堆，前者存较小一半，后者存较大一半，平衡大小差 ≤ 1。
堆排序：建堆 O(n) + n 次出堆 O(n log n)，原地排序但不稳定，且缓存局部性不如快排。

堆的难点在于边界处理和堆接口的实现细节。建议把 findKthLargest、mergeKLists、MedianFinder 三题反复手写，直到不用查阅文档。

下一篇我们将进入图的世界——DFS、BFS、最短路径、最小生成树、拓扑排序、并查集，这是数据结构中应用最广、也最有趣的章节之一。

入门篇

进阶篇

资深篇

堆与优先队列

一、堆的概念

1. 完全二叉树

2. 大顶堆、小顶堆

3. 堆的数组表示

二、堆的操作

1. 上浮（sift up）

2. 下沉（sift down）

3. 完整堆实现

三、Go 标准库：container/heap

1. heap.Interface

2. 自定义堆实现

四、优先队列

1. 基于堆实现

五、常见算法

1. 堆排序

2. Top K 问题

3. 合并 K 个有序链表（LC 23）

4. 数据流中位数（LC 295）

六、LeetCode 经典题解析

1. 数组中第 K 大元素（LC 215）

2. 前 K 个高频元素（LC 347）

3. 滑动窗口最大值（LC 239）

七、复杂度分析

八、小结

堆与优先队列 ​

一、堆的概念 ​

1. 完全二叉树 ​

2. 大顶堆、小顶堆 ​

3. 堆的数组表示 ​

二、堆的操作 ​

1. 上浮（sift up） ​

2. 下沉（sift down） ​

3. 完整堆实现 ​

三、Go 标准库：container/heap ​

1. heap.Interface ​

2. 自定义堆实现 ​

四、优先队列 ​

1. 基于堆实现 ​

五、常见算法 ​

1. 堆排序 ​

2. Top K 问题 ​

3. 合并 K 个有序链表（LC 23） ​

4. 数据流中位数（LC 295） ​

六、LeetCode 经典题解析 ​

1. 数组中第 K 大元素（LC 215） ​

2. 前 K 个高频元素（LC 347） ​

3. 滑动窗口最大值（LC 239） ​

七、复杂度分析 ​

八、小结 ​

堆与优先队列

一、堆的概念

1. 完全二叉树

2. 大顶堆、小顶堆

3. 堆的数组表示

二、堆的操作

1. 上浮（sift up）

2. 下沉（sift down）

3. 完整堆实现

三、Go 标准库：container/heap

1. heap.Interface

2. 自定义堆实现

四、优先队列

1. 基于堆实现

五、常见算法

1. 堆排序

2. Top K 问题

3. 合并 K 个有序链表（LC 23）

4. 数据流中位数（LC 295）

六、LeetCode 经典题解析

1. 数组中第 K 大元素（LC 215）

2. 前 K 个高频元素（LC 347）

3. 滑动窗口最大值（LC 239）

七、复杂度分析

八、小结