Go heap 怎样实现优先级任务队列

我第一次用 Go 写优先级任务队列时，真正容易弄错的不是“堆”这个数据结构，而是两个方向：container/heap 默认把 Less 定义的最小元素放到根部，而业务通常希望优先级数字越大越先处理。解决方法是实现一个切片类型，把比较规则反过来，再把任务的当前位置记录下来。

官方地址：https://pkg.go.dev/container/heap

用 heap.Interface 适配任务切片，用反向的 Less 让高优先级任务先出队；如果任务在队列中改变了优先级，再调用 heap.Fix 修复它所在位置。

先把 heap.Interface 的五个方法对上

标准库的 heap.Interface 嵌入了 sort.Interface，所以需要提供 Len、Less、Swap，另外还要提供供堆算法调用的 Push 和 Pop。这里的 Push 与 Pop 不是业务入口，业务代码应调用包级的 heap.Push 和 heap.Pop。

package main

import "container/heap"

// Task 是队列里的任务；index 用于优先级变化后的 Fix 定位。
type Task struct {
	Name     string
	Priority int
	Sequence uint64
	index    int
}

// PriorityQueue 用切片保存任务，并满足 heap.Interface。
type PriorityQueue []*Task

// Len 返回当前任务数量，堆算法用它判断边界。
func (pq PriorityQueue) Len() int { return len(pq) }

// Less 反向比较，让 Priority 更大的任务位于根部。
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].Priority > pq[j].Priority
}

// Swap 交换任务并同步 index，否则 Fix 无法找到任务的新位置。
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

// Push 是 heap.Push 内部调用的方法，参数必须追加到切片末尾。
func (pq *PriorityQueue) Push(x any) {
	task := x.(*Task)
	task.index = len(*pq)
	*pq = append(*pq, task)
}

// Pop 是 heap.Pop 内部调用的方法，按堆算法要求从切片尾部移除。
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	task := old[n-1]
	old[n-1] = nil // 释放切片对任务的引用，避免无意义地保留对象。
	task.index = -1
	*pq = old[:n-1]
	return task
}

var _ heap.Interface = (*PriorityQueue)(nil)

其中最关键的是 Less。文档定义的是最小堆，因此 pq[i].Priority > pq[j].Priority 会把数值更大的任务当成“更小”的堆元素，从而让它出现在根部。若你的业务约定是数字越小越紧急，就把比较符改成 ，其余实现不需要变化。

用包级函数完成入队和出队

定义好适配层后，初始化只需要一次。空切片可以直接 heap.Init，之后通过 heap.Push 添加任务，通过 heap.Pop 取出当前最高优先级任务。

func main() {
	queue := make(PriorityQueue, 0, 4)
	heap.Init(&queue) // 建立堆不变量；空队列也可以安全初始化。

	heap.Push(&queue, &Task{Name: "发送邮件", Priority: 20})
	heap.Push(&queue, &Task{Name: "刷新缓存", Priority: 50})
	heap.Push(&queue, &Task{Name: "生成报表", Priority: 30})

	for queue.Len() > 0 {
		task := heap.Pop(&queue).(*Task)
		println(task.Name, task.Priority) // 出队顺序应按高优先级到低优先级。
	}
}

这段代码的预期出队顺序是“刷新缓存、生成报表、发送邮件”。heap.Push 和 heap.Pop 的复杂度都是 O(log n)；只查看队首时不要调用 heap.Pop，直接读取 queue[0]，并先确认队列非空。

任务优先级变化后怎样调用 heap.Fix

队列里的任务不是静态数据时，常见场景是任务等待期间被提升或降级。直接修改 Priority 会破坏堆不变量，必须再调用 heap.Fix。这也是前面维护 index 字段的原因。

func updatePriority(pq *PriorityQueue, task *Task, priority int) {
	if task.index = pq.Len() {
		return // -1 表示任务已出队，避免把无效索引传给 Fix。
	}

	task.Priority = priority
	heap.Fix(pq, task.index) // 让任务向新位置上浮或下沉。
}

如果只是把任务从队列中删除，使用 heap.Remove(&queue, task.index)，不要手动 append 或切片删除，因为那样不会自动修复其他节点的位置。

三个容易让队列行为看起来异常的边界

空队列不能直接读取 queue[0]

读取队首前先检查 Len。heap.Pop 也要求队列中有元素，若业务层允许空队列，应把检查放在统一的 Dequeue 封装中。

同优先级不等于稳定顺序

堆只保证根部是当前最小元素（本例中是业务上的最高优先级），不会自动保证同优先级任务按照进入顺序出队。如果需要稳定顺序，可以给任务增加自增的 Sequence，在优先级相等时比较序号。

func (pq PriorityQueue) Less(i, j int) bool {
	if pq[i].Priority != pq[j].Priority {
		return pq[i].Priority > pq[j].Priority // 先比较业务优先级。
	}
	return pq[i].Sequence 

并发访问需要额外的同步层

container/heap 只负责堆操作，不提供互斥保护。多个 goroutine 同时入队、出队或更新任务时，应在队列封装层使用 sync.Mutex 或把操作串行化；不要把裸的 PriorityQueue 直接共享给并发调用方。

把接口、方向和更新规则记成一张表

回头看，这个实现的核心并不在于手写上浮、下沉算法，而在于把业务任务映射成满足接口的切片：Less 决定优先级方向，Swap 保持索引一致，包级函数负责维护结构，Fix 处理队列中任务的动态变化。只要这四个关系没有混在一起，优先级任务队列就容易扩展。

相关问题

Go heap 默认是大顶堆吗？不是。它按 Less 定义维护最小堆；业务上想让大数字优先，需要反向实现 Less。

为什么不能直接调用自定义的 Push 方法？因为自定义方法只是供堆算法完成切片追加，真正的上浮和不变量维护由 heap.Push 完成。

修改 Priority 后没有重新排序怎么办？保存任务当前的 index，修改字段后调用 heap.Fix；任务已出队时不要再修复。