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 这个变量，比盯函数名重要得多。
