堆

基础与数据结构

说明

维持父节点不大于子节点的最小堆；插入与取最小值都是 O(log n)。

分析

最小堆只保证根是最小值，不保证整个切片有序。Push 沿父节点向上调整，Pop 把末尾元素放到根后沿较小子节点向下调整。

最小堆只要求父值不大于孩子，兄弟间不必有序。删除根后把末尾放到根，再沿较小孩子向下恢复约束；每次只走一条树高路径。读取最小值是O(1)，删除并修复才是O(log n)。

查看图表代码

适用前提与边界

优先队列和 Top K 常用堆；访问任意非根元素仍可能要线性查找。 空堆不能Pop；堆只保证父子大小关系，不支持直接通过下标找到某个指定值。

示例输入与调用

h := new(MinHeap)
	h.Push(5)
	h.Push(2)
	fmt.Println(h.Pop())

运行输出

2

完整 Go 示例

package main

import "fmt"

type MinHeap []int

func (h *MinHeap) Push(x int) {
	*h = append(*h, x)
	for i := len(*h) - 1; i > 0; {
		p := (i - 1) / 2
		if (*h)[p] <= (*h)[i] {
			break
		}
		(*h)[p], (*h)[i] = (*h)[i], (*h)[p]
		i = p
	}
}
func (h *MinHeap) Pop() int {
	out := (*h)[0]
	last := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	if len(*h) == 0 {
		return out
	}
	(*h)[0] = last
	for i := 0; 2*i+1 < len(*h); {
		c := 2*i + 1
		if c+1 < len(*h) && (*h)[c+1] < (*h)[c] {
			c++
		}
		if (*h)[i] <= (*h)[c] {
			break
		}
		(*h)[i], (*h)[c] = (*h)[c], (*h)[i]
		i = c
	}
	return out
}

func main() {
	h := new(MinHeap)
	h.Push(5)
	h.Push(2)
	fmt.Println(h.Pop())
}