如何在 Go 中使用 heap 包实现优先队列-Golang-PHP中文网

go的heap包不提供现成类型，需自定义类型实现heap.interface的5个方法；push/pop必须指针接收者且返回interface{}；堆序由less方法决定，最小堆返回a[i]

如何在 go 中使用 heap 包实现优先队列

为什么直接用 `heap` 包不能直接 new 一个优先队列

Go 标准库的 heap 包不是提供一个开箱即用的类型，而是一组操作函数（heap.Init、heap.Push、heap.Pop 等），作用于满足 heap.Interface 的切片。这意味着你必须自己定义底层数据结构，并实现 Len、Less、Swap、Push、Pop 五个方法。

常见错误是试图写 q := heap.NewPriorityQueue() 或直接对 []int 调用 heap.Push —— 这会编译失败，因为基础切片不满足接口。

必须定义一个命名类型（如 IntHeap）包装切片
Push 和 Pop 方法签名必须是 func(*T, interface{}) 和 func(*T) interface{}，注意是指针接收者 + 返回 interface{}
Pop 实际上要从切片末尾取元素并缩短长度，不是“弹出堆顶”——堆顶移除由 heap.Pop 内部调用 Pop 后再 down 调整完成

最小堆与最大堆只差一行 `Less` 实现

Go 的 heap 本身不区分大小堆，完全由你实现的 Less(i, j int) bool 决定排序逻辑。想建最小堆就写 a[i] ，最大堆就写 <code>a[i] > a[j]。

星火文档问答

星火文档问答是基于讯飞星火大模型的AI文档和知识库问答助手。

下载

例如处理任务调度时按优先级数字升序（数字越小越紧急），就用最小堆；若按分数降序（高分优先），就用最大堆。

别在 Less 里写 return i —— 这比较的是索引，不是元素值
如果元素是结构体，Less 中需显式解引用：比如 h[i].Priority
浮点数比较慎用 == 或直接 ，建议先考虑是否需加 epsilon 或转为整数倍数处理

`heap.Push` 和 `heap.Pop` 必须配合指针使用

所有 heap 函数都要求传入指向切片的指针（*[]T），否则修改无法反映到原变量。这是最容易被忽略的 panic 来源。

// ✅ 正确：传 &h
h := &IntHeap{1, 3, 2}
heap.Init(h)

// ❌ 错误：传 h（值拷贝），Init 后 h 仍是空或未调整
heap.Init(h)

heap.Push(&h, 5)：内部会调用 h.Push(5)，然后做 up 调整
v := heap.Pop(&h)：先调用 h.Pop() 取走末尾元素，再把堆顶和末尾交换、缩短切片、down 调整，最后返回原堆顶值
如果忘记取地址，程序可能不报错但行为异常（比如始终 Pop 出零值、堆不更新）

自定义类型中 `Push`/`Pop` 的典型写法

这两个方法是唯一允许修改切片长度的地方，也是唯一能访问到底层数据的方式。它们不负责堆性质维护（那是 heap 函数的事），只负责“放进去”和“拿出来”的动作本身。

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1] // 注意：不是 old[:n-1]，要保留底层数组容量
    return item
}