Go语言基于自定义KeyValue类型实现heap堆排序不生效问题

问题排查结论 #

• 你实现的heap.Interface接口完全正确，Swap、Push、Pop方法没有逻辑错误
• 你观察到的heap.Init之后切片没有完全有序是二叉堆数据结构的正常特性，不是Bug

原理说明 #

二叉堆（你实现的是最小堆）仅保证两个核心特性：

1. 堆顶元素（即切片索引0的位置）是整个集合的最小元素
2. 任意父节点的值小于等于它的所有子节点的值
   它不会保证整个切片是升序排列的，堆初始化heap.Init的时间复杂度为O(n)，本身不会执行全排序操作。

验证方法 #

如果需要获取按Key升序排列的所有元素，在heap.Init之后循环调用heap.Pop()即可，每次弹出的都是当前剩余元素中的最小值，输出顺序就是完全有序的，示例代码如下：

heap.Init(kv1)
// 循环弹出获取有序序列
for kv1.Len() > 0 {
    elem := heap.Pop(kv1).(KeyValue)
    fmt.Printf("%s ", elem.Key)
}
// 对应你的测试用例输出结果为：3 3 5 5 6 7 7 7 8 8 9，完全符合升序预期

内容的提问来源于stack exchange，提问作者shengjiang