golang如何实现堆排序_golang堆排序实现步骤

Go 标准库的 container/heap 包，常被人误当成堆排序的直接实现。但真相是：它只维护堆性质（最大堆或最小堆），并不负责把元素逐个弹出再填回原数组完成排序。它本质上是个优先队列工具，和 sort.Sort 那种开箱即用的排序器不是一回事。想真正实现堆排序，得自己走「建堆 + 反复取顶 + 调整」三步，而且必须用 heap.Fix 或手写 siftDown —— 直接调 heap.Pop 会改变切片长度，原地排序的前提就没了。

Go 标准库的 heap 包不是堆排序，别直接拿来当排序用

很多人看到 container/heap 就以为能直接做堆排序，结果调用 heap.Init 后数组没变有序——因为这个包只维护堆性质，不负责把元素逐个弹出并填回原数组。它本质是优先队列，不是 sort.Sort 那种开箱即用的排序器。真正实现堆排序，得自己写「建堆 + 反复取顶 + 调整」三步逻辑，且必须用 heap.Fix 或手写 siftDown，不能只靠 heap.Pop——后者会改变切片长度，破坏原地排序前提。

• heap.Init 只做一次堆化，不排序
• heap.Pop 返回值并 append 到新切片？那是额外空间 O(n)，不算“原地”
• 想原地排升序，得建最大堆，然后把堆顶和末尾交换，再对剩余部分 siftDown

手写 siftDown 比依赖 heap 包更可控、更符合堆排序语义

标准库 heap 要求你实现 heap.Interface，但排序时你并不需要持久化堆结构，只需临时调整。手写一个内联 siftDown 函数，参数明确：切片、起始索引、边界长度。没有接口抽象开销，也避免误用 heap.Remove 这类高危操作。注意下标计算：左子节点是 2*i + 1，右子是 2*i + 2，父节点是 (i-1)/2；比较和交换必须严格在 [0, heapSize) 范围内，越界就停。

func siftDown(data []int, i, heapSize int) {
    for {
        l, r := 2*i+1, 2*i+2
        largest := i
        if l < heapSize && data[l] > data[largest] {
            largest = l
        }
        if r < heapSize && data[r] > data[largest] {
            largest = r
        }
        if largest == i {
            break
        }
        data[i], data[largest] = data[largest], data[i]
        i = largest
    }
}

建堆阶段从最后一个非叶子节点开始，不是从 0 或 len-1

完全二叉树中，最后一个非叶子节点下标是 (len(data) - 1) / 2（整数除法），从它开始往前 siftDown，才能保证每个子树都满足堆性质。如果从 0 开始，会重复调整；如果从 len-1 开始，叶子节点调了也没用，纯属浪费。

• 输入 []int{3, 1, 4, 1, 5}，长度 5 → 最后非叶节点索引是 (5-1)/2 = 2
• 所以建堆循环是 for i := (len(data)-1)/2; i >= 0; i--
• 这一步时间复杂度是 O(n)，不是 O(n log n)，很多人误以为建堆要逐个 Push

排序主循环必须「交换堆顶 ↔ 当前末尾，然后缩小堆范围」

升序排列用最大堆：每次把 data[0]（当前最大）和 data[heapSize-1] 交换，然后对 data[0:heapSize-1] 执行 siftDown(0)。关键点是 heapSize 必须递减，且 siftDown 的第三个参数要传新长度，否则调整范围没变，后续交换就乱了。容易错在：忘了改 heapSize，或者 siftDown 里用了 len(data) 而不是传入的 heapSize，导致越界或无效调整。

func HeapSort(data []int) {
    n := len(data)
    // 建堆
    for i := (n - 1) / 2; i >= 0; i-- {
        siftDown(data, i, n)
    }
    // 排序
    heapSize := n
    for heapSize > 1 {
        data[0], data[heapSize-1] = data[heapSize-1], data[0]
        heapSize--
        siftDown(data, 0, heapSize)
    }
}

堆排序真正的坑不在算法逻辑，而在下标边界和堆范围的动态管理——少一个 -1，多一次 len()，结果就静默错乱。写的时候盯着 heapSize 这个变量，比盯函数名重要得多。