Go语言如何实现堆_Go语言堆数据结构教程【详解】-Golang-PHP中文网

go语言无内置堆类型，需通过container/heap包配合自定义类型实现，该类型必须实现len、less、swap三个方法，且less决定堆序方向。

go语言如何实现堆_go语言堆数据结构教程【详解】

Go 语言里没有内置的 `heap` 类型，只有 `container/heap` 包

Go 不像 Python 有 heapq 或 Java 有 PriorityQueue 那样开箱即用的堆类型。它把“堆”抽象成一种接口契约，由你提供底层数据结构（通常是切片），再通过 container/heap 提供的函数来维护堆序。这意味着：你得自己定义比较逻辑，也得自己管好底层数组的增删——heap.Push 和 heap.Pop 不会自动扩容或收缩切片，它们只调用你实现的 Less、Swap、Len 方法。

常见错误现象：

忘记在 Push 前用 append 扩容切片，导致 panic：index out of range
实现 Less(i, j int) bool 时写反了大小关系，结果最小堆变最大堆（或反之）却没意识到
直接修改切片元素后没调用 heap.Fix，堆序被破坏，后续 Pop 返回错误值

实现最小堆必须满足 `heap.Interface` 的三个方法

你得让自己的类型实现 Len()、Less(i, j int) bool、Swap(i, j int)。缺一不可，否则编译不过。注意：Less 决定堆序方向——返回 true 表示索引 i 对应的元素“优先级更高”，也就是该排在堆顶。最小堆就写 a[i] ，最大堆写 <code>a[i] > a[j]。

实操建议：

类型最好用命名切片，比如 type IntHeap []int，别用匿名结构体套切片，否则 Len 等方法写起来啰嗦
Less 中务必做边界检查（虽然 container/heap 调用时通常合法，但调试时自己手调可能越界）
Swap 必须原地交换，不能只改副本；切片本身是引用，但元素是值，所以要显式赋值

示例片段：

Go语言（Golang）1.26.0

Go语言（Golang）1.26.0版本官方下载，版本号 1.26.0，适合旧项目维护、兼容性测试和指定版本开发环境搭建。

下载

type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] 

<h3>
<code>heap.Push</code> 和 <code>heap.Pop</code> 不是“原子操作”，要配对使用 <code>append</code> 和切片截断</h3>
<p><code>heap.Push(&h, x)</code> 内部会调用你的 <code>Push</code> 方法（如果实现了），但标准用法里你**不实现 <code>Push</code>**，而是传入一个指针 + 值，它内部先 <code>append</code> 再 <code>up</code>。所以你必须确保传入的是切片地址，且该切片可被修改。同理，<code>heap.Pop</code> 返回堆顶后，会自动把最后一个元素移到顶部再 <code>down</code>，但不会自动切掉末尾——你得自己在调用后做 <code>h = h[:len(h)-1]</code>，否则下次 <code>Len()</code> 还是旧长度，堆序错乱。</p>
<p>容易踩的坑：</p>

传值调用 heap.Push(h, x)（没取地址），修改无效
调用 heap.Pop(&h) 后忘了 h = h[:h.Len()-1]，导致重复 pop 同一个旧值
用 make([]int, 0) 初始化后直接 heap.Init(&h) 没问题，但后续 Push 前必须保证切片可增长（append 是安全的）

性能关键点：堆操作是 O(log n)，但切片扩容是均摊 O(1)，别在循环里反复 `make`

如果你在循环中不断新建堆（比如每次处理一批数据都 make(IntHeap, 0)），GC 压力会上升，而且初始化 heap.Init 是 O(n)。更高效的做法是复用切片：声明一次 h := make(IntHeap, 0, 1024)，用完后 h = h[:0] 清空，再 heap.Init(&h) 重置。注意 h[:0] 不释放底层数组内存，所以后续 append 只要不超 cap 就无分配。

兼容性提醒：