Go 优先队列元素优先级改变后怎么用 heap.Fix 重新排序

Go 的优先队列元素变更优先级后，最小改动是：先修改元素字段，再用它当前的堆索引调用 heap.Fix。不要把切片直接改完就继续 heap.Pop，也不要每次都 Remove 后重新 Push。前者可能破坏堆序，后者能工作但多了一次无必要的搬运。

先把 priority 和 index 绑定起来

container/heap 并不知道业务元素在哪里。可修改优先级的队列通常让每个 Item 自己保存当前下标，队列的 Swap 在堆调整时同步更新它。下面用“数值越大优先级越高”的规则，方便观察出队顺序。

package main

import "container/heap"

type Item struct {
	value    string // 队列中要处理的业务值。
	priority int    // 数值越大，越早被取出。
	index    int    // 当前元素在堆切片中的位置。
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	// 反向比较，让 heap.Pop 返回最高优先级元素。
	return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	// 堆内部会交换元素；索引也必须跟着交换后的对象更新。
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
	item := x.(*Item)
	item.index = len(*pq) // 新元素先记录追加位置。
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	last := len(old) - 1
	item := old[last]
	old[last] = nil  // 释放队列对元素的引用，避免无意义地留住对象。
	item.index = -1  // -1 表示元素已经不在队列中。
	*pq = old[:last]
	return item
}

func updatePriority(pq *PriorityQueue, item *Item, priority int) {
	if item.index = pq.Len() {
		return // 出队或索引失效时，不再调用 Fix。
	}
	item.priority = priority // 先改值，再让 heap.Fix 修复相邻路径。
	heap.Fix(pq, item.index)
}

修改元素后，Fix 会向正确方向修复

调用顺序很重要：priority 必须先写入，heap.Fix 才能根据新旧关系判断元素应该向上还是向下移动。优先级变高时，它可能一路向根部上浮；优先级变低时，它可能下沉。调用方不需要猜方向，也不应手动交换切片。

func main() {
	pq := PriorityQueue{
		&Item{value: "普通任务", priority: 2, index: 0},
		&Item{value: "批处理任务", priority: 1, index: 1},
		&Item{value: "告警任务", priority: 4, index: 2},
	}
	heap.Init(&pq) // 初始化后，Init 会通过 Swap 重新维护 index。

	item := pq[1]
	updatePriority(&pq, item, 6) // 把批处理任务提升为最高优先级。

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		println(item.priority, item.value) // 依次观察 6、4、2 的出队顺序。
	}
}

这里的 heap.Init 只负责建立初始堆；动态更新阶段使用 Fix。官方文档把“修改索引处的值后再调用 Fix”定义为比 Remove 加重新插入更省的做法，复杂度为 O(log n)。

按这张清单排查 Fix 不生效

如果业务一次性修改了很多元素，逐个调用 Fix 未必比重新构建更合适；本文只讨论单个元素已经定位、优先级发生变化的场景。另一个边界是并发：container/heap 本身没有锁，队列和元素更新需要由调用方统一保护。

常见问题

修改 priority 后可以直接调用 heap.Init 吗？

可以重新建立整个堆，但它的复杂度是 O(n)。已知单个元素索引时，heap.Fix 更贴合动态更新。

为什么只维护 Item.index 还不够？

索引会随着堆内部交换而变化，所以必须由 Swap 持续同步；只在创建元素时写一次，后续很快就会失真。

元素出队后还能复用 updatePriority 吗？

不能。出队元素不再属于堆，应该先重新设置业务状态并通过 heap.Push 重新入队，不能拿旧索引调用 Fix。