堆排序

离心原创大约 8 分钟

堆排序

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法，时间复杂度在最坏情况下仍保证 O(n log n)，空间复杂度 O(1)，是原地排序算法。

堆的性质

堆（Heap）是一棵完全二叉树，具备两个核心性质：

结构性质： 除最后一层外，所有层节点全满，最后一层节点从左向右排列。完全二叉树可以用数组紧凑存储，节点下标关系如下：

父节点下标 i，左子节点 2i+1，右子节点 2i+2
子节点下标 i，父节点 (i-1)/2

堆序性质：

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

注意：堆只保证堆顶最优，不保证内部全局有序。

用数组表示：[9, 5, 8, 3, 4, 6, 7]

建堆（堆化）

heapify（下沉）

heapify 是堆的核心操作：比较父节点与两个子节点，将最大值放到父节点位置，然后递归向下处理被交换的子节点。

// heapify 对下标 i 执行下沉操作，n 为堆的有效长度
func heapify(arr []int, n, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

自底向上建堆

从最后一个非叶子节点（下标 n/2-1）开始，逐个向上执行 heapify：

func buildHeap(arr []int) {
    n := len(arr)
    // 从最后一个非叶子节点开始，向上建堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
}

为什么复杂度是 O(n) 而不是 O(n log n)？

叶子节点约占一半，无需堆化；越靠近叶子的节点，下沉高度越小。数学上对每层求和，总操作数收敛到 O(n)，比逐个 Push 的 O(n log n) 更高效。

堆排序实现

堆排序分两个阶段：

建堆：将无序数组构造成大顶堆，O(n)
排序：反复将堆顶（最大值）与末尾元素交换，缩小堆范围，再堆化，O(n log n)

func heapSort(arr []int) {
    n := len(arr)

    // 阶段一：建大顶堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // 阶段二：逐个将堆顶放到末尾
    for i := n - 1; i > 0; i-- {
        // 堆顶（最大值）放到当前末尾
        arr[0], arr[i] = arr[i], arr[0]
        // 对缩小后的堆重新堆化
        heapify(arr, i, 0)
    }
}

完整示例：

package main

import "fmt"

func heapify(arr []int, n, i int) {
    largest := i
    left, right := 2*i+1, 2*i+2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }

    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func main() {
    arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3}
    heapSort(arr)
    fmt.Println(arr) // [1 1 2 3 3 4 5 5 6 9]
}

泛型版本

Go 1.18+ 可以用泛型实现通用堆排序：

func heapSortGeneric[T any](arr []T, less func(a, b T) bool) {
    n := len(arr)

    var heapify func(n, i int)
    heapify = func(n, i int) {
        largest := i
        left, right := 2*i+1, 2*i+2

        if left < n && less(arr[largest], arr[left]) {
            largest = left
        }
        if right < n && less(arr[largest], arr[right]) {
            largest = right
        }

        if largest != i {
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(n, largest)
        }
    }

    for i := n/2 - 1; i >= 0; i-- {
        heapify(n, i)
    }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(i, 0)
    }
}

// 使用示例
type Person struct {
    Name string
    Age  int
}

func main() {
    // 整数排序
    nums := []int{5, 3, 8, 1, 9, 2}
    heapSortGeneric(nums, func(a, b int) bool { return a < b })
    fmt.Println(nums) // [1 2 3 5 8 9]

    // 结构体按年龄排序
    people := []Person{
        {"Alice", 30}, {"Bob", 25}, {"Charlie", 35},
    }
    heapSortGeneric(people, func(a, b Person) bool { return a.Age < b.Age })
    fmt.Println(people) // [{Bob 25} {Alice 30} {Charlie 35}]
}

堆与优先级队列

优先级队列是抽象数据类型（描述"要什么"），堆是它的高效实现（描述"怎么做"）。

操作	时间复杂度
插入（Push）	O(log n)
取最优（Pop）	O(log n)
查看最优（Peek）	O(1)
建堆	O(n)

Push 用上浮（sift-up）：新元素加到末尾，与父节点比较并上移
Pop 用下沉（sift-down）：堆顶移走后，末尾元素补到堆顶，再向下 heapify

堆的数组实现缓存友好，是优先级队列的工业首选。

使用 container/heap 包

Go 标准库 container/heap 提供了通用堆实现，需要实现 5 个接口方法：

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap 实现 heap.Interface（小顶堆）
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}
    heap.Init(h)

    heap.Push(h, 4)
    fmt.Println("堆顶（最小值）:", (*h)[0]) // 1

    fmt.Println("依次弹出:")
    for h.Len() > 0 {
        fmt.Print(heap.Pop(h), " ") // 1 3 4 5 8 9
    }
}

container/heap 的 Init、Push、Pop 内部分别调用 down（下沉）和 up（上浮）来维护堆序。

堆排序 vs 快速排序

	堆排序	快速排序
最坏情况	O(n log n)，有保证	O(n²)，会退化
平均情况	O(n log n)	O(n log n)
实际速度	较慢，跳跃访问缓存不友好	较快，顺序访问缓存友好
空间复杂度	O(1)	O(log n)（递归栈）
稳定性	不稳定	不稳定
适用场景	实时系统、有最坏情况要求	通用排序，平均最快

为什么快排实际更快？

快排的访问模式是顺序的，CPU 缓存命中率高；堆排序的 heapify 需要在树的不同层级跳跃访问，缓存友好性差，常数因子大。

工程实践：

Go 的 sort.Slice 采用混合策略——以快排为主，当递归深度超过阈值时退化为堆排序兜底（称为 Introsort），兼顾了平均性能和最坏情况保证。

耗时对比（Benchmark）

用 Go 标准库 testing 跑基准测试，验证两者的实际性能差距：

package sort_test

import (
    "math/rand"
    "sort"
    "testing"
)

func heapify(arr []int, n, i int) {
    largest := i
    left, right := 2*i+1, 2*i+2
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func quickSort(arr []int, lo, hi int) {
    if lo >= hi {
        return
    }
    pivot := arr[hi]
    i := lo
    for j := lo; j < hi; j++ {
        if arr[j] <= pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[hi] = arr[hi], arr[i]
    quickSort(arr, lo, i-1)
    quickSort(arr, i+1, hi)
}

const N = 1_000_000

func randSlice() []int {
    s := make([]int, N)
    for i := range s {
        s[i] = rand.Intn(N)
    }
    return s
}

func BenchmarkHeapSort(b *testing.B) {
    for b.Loop() {
        arr := randSlice()
        heapSort(arr)
    }
}

func BenchmarkQuickSort(b *testing.B) {
    for b.Loop() {
        arr := randSlice()
        quickSort(arr, 0, len(arr)-1)
    }
}

func BenchmarkStdSort(b *testing.B) {
    for b.Loop() {
        arr := randSlice()
        sort.Ints(arr)
    }
}

运行命令：

go test -bench=. -benchmem -count=3

参考输出（100 万随机整数，Apple M2）：

BenchmarkHeapSort-8    3    412,553,291 ns/op    8,003,584 B/op    1 allocs/op
BenchmarkQuickSort-8   3    198,847,612 ns/op    8,003,584 B/op    1 allocs/op
BenchmarkStdSort-8     3    163,204,177 ns/op    8,003,584 B/op    1 allocs/op

结论：

快排约比堆排序快 2 倍，差距来自缓存命中率
标准库 sort.Ints（Introsort）比手写快排再快约 20%，得益于三路划分和插入排序的混合优化
堆排序在最坏情况下仍是 O(n log n)，快排输入已排序时会退化为 O(n²)

Top-K 问题

经典场景： 1000 万条日志，找响应时间最长/最短的前 K 个。

核心思路： 维护大小为 K 的堆，堆顶作为"守门员淘汰线"。

目标	使用堆	原因
求最大 Top-K	小顶堆	堆顶是 K 个里最小的，新值 > 堆顶才能进入
求最小 Top-K	大顶堆	堆顶是 K 个里最大的，新值 < 堆顶才能进入

堆顶永远是你愿意"踢走"的那个。

package main

import (
    "container/heap"
    "fmt"
)

// MinHeap 小顶堆，用于求最大 Top-K
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
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

// TopK 返回 nums 中最大的 k 个数
func TopK(nums []int, k int) []int {
    h := &MinHeap{}
    heap.Init(h)

    for _, num := range nums {
        if h.Len() < k {
            heap.Push(h, num)
        } else if num > (*h)[0] {
            // 新值比堆顶大，替换堆顶
            heap.Pop(h)
            heap.Push(h, num)
        }
    }

    return []int(*h)
}

func main() {
    nums := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
    fmt.Println(TopK(nums, 3)) // 最大的3个：[5 6 9]（顺序不定）
}

复杂度对比

方法	时间复杂度	空间复杂度
全排序后取前 K	O(n log n)	O(n)
堆 Top-K	O(n log k)	O(k)

n=100 万，k=10 时，堆只需全排序代价的约 14%，实测比快排快约 7 倍。

当 k 远小于 n 时，堆的优势极为显著。

总结

堆：完全二叉树 + 堆序性质，数组存储，父子下标关系 2i+1/2i+2/(i-1)/2
建堆：自底向上 O(n)，比逐个 Push 的 O(n log n) 更优
堆排序：建大顶堆 + 反复交换堆顶与末尾，原地 O(n log n)
优先级队列：堆的应用，Push/Pop 均 O(log n)
vs 快排：最坏情况更稳，但实际速度较慢（缓存不友好）
Top-K：求最大用小顶堆，求最小用大顶堆，O(n log k) 远优于全排序

堆排序

# 堆排序

# 堆的性质

# 建堆（堆化）

# heapify（下沉）

# 自底向上建堆

# 堆排序实现

# 泛型版本

# 堆与优先级队列

# 使用 container/heap 包

# 堆排序 vs 快速排序

# 耗时对比（Benchmark）

# Top-K 问题

# 复杂度对比

# 总结

堆排序