Heap
堆（Heap）是一种完全二叉树结构，常用于快速取得当前的最大值或最小值。它不是完全排序，而是 partial ordered：
- 在大顶堆（max-heap）中，每个父节点都大于等于它的子节点，因此根节点一定是最大值。
- 在小顶堆（min-heap）中，每个父节点都小于等于它的子节点，因此根节点一定是最小值。
堆只保证父子之间的局部有序，并不保证兄弟节点或不同子树之间有序。它和 binary search tree 的区别是：
- heap：父节点和子节点之间满足大小关系，因此只能快速拿到堆顶（全局最大或最小）。
- BST：左子树 < 根 < 右子树，维护的是更强的全局有序关系，所以中序遍历会得到有序序列。
- heap 适合 priority queue；BST 更适合查找某个具体值、范围查询、顺序遍历。
正因为只维护这种局部顺序，堆可以高效支持：
- 插入一个元素：$O(\log n)$
- 删除堆顶元素：$O(\log n)$
- 查看堆顶元素：$O(1)$
- 从无序数组建堆：$O(n)$
在算法题里，堆通常作为 priority queue 使用，用来动态维护“当前最小/最大”的元素，比如：
- Top K
- Dijkstra / A*
- merge k sorted lists
- streaming median
由于堆是完全二叉树，所以通常直接用数组表示，而不需要真的定义树节点。
Build Heap with array
对 0-based array 来说，如果某个节点的下标是 k，那么：
- left child =
2k + 1 - right child =
2k + 2 - parent =
(k - 1) / 2
为什么会是这个公式？
因为完全二叉树每一层都是从左到右紧密排列的。第 i 层一共有 2^i 个节点，而前面所有层的节点总数是：
2^i - 1
如果某个节点位于第 i 层、并且它是这一层从左往右第 d 个节点，那么它在数组中的下标就是：
k = (2^i - 1) + d
它的左孩子位于下一层，并且仍然对应第 2d 个位置，所以左孩子下标为：
(2^(i+1) - 1) + 2d = 2((2^i - 1) + d) + 1 = 2k + 1
同理，右孩子下标就是 2k + 2。
func buildHeap(nums []int) {
size := len(nums)
// k, 2k+1, 2k+2; k = (i-1)/2
for i := size/2 - 1; i >= 0; i++ {
siftDown(nums, i)
}
}
func pop(heap []int) int {
// switch to end and sift down
item := heap[0]
heap[0] = heap[len(heap)-1]
heap = heap[:len(heap)-1]
siftDown(heap, 0)
return item
}
func push(heap []int, item int) []int {
// append to end and sift up
heap = append(heap, item)
siftUp(heap, len(heap)-1)
// here we created new slice and return it
return heap
}
func siftUp(nums []int, i int) {
if i <= 0 {
return
}
parent := (i - 1) / 2
if nums[parent] > nums[i] {
nums[i], nums[parent] = nums[parent], nums[i]
siftUp(nums, parent)
}
}
func siftDown(nums []int, i int) {
size := len(nums)
smallest := i
l, r := 2*i+1, 2*i+2
if l < size && nums[l] < nums[smallest] {
smallest = l
}
if r < size && nums[r] < nums[smallest] {
smallest = r
}
if smallest != i {
nums[i], nums[smallest] = nums[smallest], nums[i]
siftDown(nums, smallest)
}
}
Heap Building & Sift Process
堆的构建通常采用 siftDown（下沉）操作，从最后一个非叶子节点开始，自底向上进行堆化。其时间复杂度为 $O(n)$。
SiftDown 过程
- 比较当前节点与左右子节点的值。
- 在三者中找到最小（小顶堆）或最大（大顶堆）的节点。
- 如果最小/最大节点不是当前节点，则交换它们，并对交换后的子节点递归执行
siftDown。
堆构建流程可视化 (Min-Heap)
以 [7, 2, 5, 8, 1, 6, 4] 为例，堆构建从最后一个非叶子节点（index = 2, value = 5）开始：
Go Heap lib
import (
"container/heap"
"fmt"
)
type Cell struct {
dx int
dy int
height int
}
type PriorityQueue []*Cell
func (pq PriorityQueue) Len() int {
return len(pq)
}
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].height < pq[j].height
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x any) {
item := x.(*Cell)
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() any {
n := len(*pq)
item := (*pq)[n-1]
*pq = (*pq)[0 : n-1]
return item
}
func main() {
cells := [][3]int{
{0, 0, 7},
{0, 1, 2},
{0, 2, 5},
}
pq := make(PriorityQueue, 3)
for i := 0; i < 3; i++ {
pq[i] = &Cell{cells[i][0], cells[i][1], cells[i][2]}
}
heap.Init(&pq)
for pq.Len() > 0 {
val := heap.Pop(&pq)
fmt.Println(val)
}
}
implementation source heap.go