1. Go语言中优先队列的基础：container/heap包
在Go语言中，标准库提供了container/heap包来实现堆（heap）数据结构，它是构建优先队列的基础。container/heap包本身不直接提供一个开箱即用的优先队列类型，而是提供了一组操作（如heap.Init、heap.Push、heap.Pop），这些操作作用于任何实现了heap.Interface接口的类型。
heap.Interface接口定义如下：
package heap
import "sort"
type Interface interface {
sort.Interface // 包含 Len(), Less(i, j int), Swap(i, j int)
Push(x any) // 将 x 添加到堆中
Pop() any // 移除并返回堆顶元素
}这意味着，要使用container/heap包，开发者需要为自己的数据类型实现这个接口。在Go 1.18引入泛型之前，这意味着每当需要一个不同数据类型的优先队列时，都需要重新定义并实现一套heap.Interface。
2. 特定类型优先队列的实现（Go泛型前）
在Go泛型出现之前，如果需要一个优先队列来存储特定类型的元素（例如，带有优先级的任务），开发者必须为该特定类型定义一个数据结构，并使其实现heap.Interface。
立即学习“go语言免费学习笔记（深入）”；
2.1 定义元素和优先队列类型
假设我们需要一个优先队列来存储具有字符串值和整数优先级的任务。
package main
import (
"container/heap"
"fmt"
)
// Item 表示优先队列中的一个元素
type Item struct {
Value string // 元素值
Priority int // 优先级，数字越小优先级越高
Index int // 在堆中的索引，用于更新（可选，但对于 Update 操作很有用）
}
// PriorityQueue 实现了 heap.Interface 接口，是一个 Item 指针的切片
type PriorityQueue []*Item2.2 实现 heap.Interface 方法
接下来，需要为PriorityQueue类型实现Len(), Less(i, j int), Swap(i, j int), Push(x any), Pop() any方法。
// 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 交换索引 i 和 j 处的元素
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].Index = i // 更新元素在堆中的索引
pq[j].Index = j
}
// Push 将元素 x 添加到队列中
func (pq *PriorityQueue) Push(x any) {
n := len(*pq)
item := x.(*Item) // 类型断言
item.Index = n
*pq = append(*pq, item)
}
// Pop 移除并返回队列中优先级最高的元素
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil // 避免内存泄露
item.Index = -1 // 用于表示该元素已不在堆中
*pq = old[0 : n-1] // 移除最后一个元素
return item
}
// Update 修改指定 Item 的优先级和值，并调整堆结构
func (pq *PriorityQueue) Update(item *Item, value string, priority int) {
item.Value = value
item.Priority = priority
heap.Fix(pq, item.Index) // 重新调整堆结构以保持堆属性
}2.3 示例使用
func main() {
// 创建一些 Item
items := map[string]int{
"task1": 3,
"task2": 1,
"task3": 4,
"task4": 2,
}
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
pq[i] = &Item{
Value: value,
Priority: priority,
Index: i,
}
i++
}
heap.Init(&pq) // 初始化堆
// 添加新元素
item5 := &Item{Value: "task5", Priority: 0}
heap.Push(&pq, item5)
pq.Update(item5, item5.Value, 5) // 更新 item5 的优先级
// 弹出元素
fmt.Println("按优先级顺序弹出元素:")
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item) // 类型断言
fmt.Printf("优先级: %d, 值: %s\n", item.Priority, item.Value)
}
// 预期输出 (优先级从小到大):
// 优先级: 1, 值: task2
// 优先级: 2, 值: task4
// 优先级: 3, 值: task1
// 优先级: 4, 值: task3
// 优先级: 5, 值: task5
}注意事项：
- 这种方法为每种需要优先队列的特定数据类型，都要求重复实现heap.Interface，导致代码重复。
- Push和Pop方法的参数和返回值类型为any，这意味着在使用时需要进行类型断言，这增加了运行时错误的风险。
3. 可重用优先队列的实现（Go泛型，Go 1.18+）
Go 1.18引入了泛型（Generics），这彻底改变了在Go中实现可重用数据结构的方式。现在，我们可以创建一个通用的优先队列，它能够处理任何类型的元素，而无需为每种类型重复编写heap.Interface的实现。关键在于将元素的比较逻辑作为参数传入。
3.1 定义泛型优先队列类型
我们可以创建一个泛型结构体GenericPriorityQueue[T]，它包含一个存储元素的切片和一个用于比较元素的函数less。
package main
import (
"container/heap"
"fmt"
)
// GenericPriorityQueue 实现了 heap.Interface 接口，可用于任何类型 T，
// 只要提供了正确的比较函数。
type GenericPriorityQueue[T any] struct {
items []T
less func(a, b T) bool // 比较函数，定义优先级
}3.2 实现 heap.Interface 方法（泛型版）
Len(), Swap() 方法的实现与之前类似，但Less()方法将使用传入的less函数。Push()和Pop()仍需处理any类型，但其内部逻辑是通用的。
// Len 返回队列中的元素数量
func (pq GenericPriorityQueue[T]) Len() int {
return len(pq.items)
}
// Less 比较索引 i 和 j 处的元素优先级，使用传入的 less 函数
func (pq GenericPriorityQueue[T]) Less(i, j int) bool {
return pq.less(pq.items[i], pq.items[j])
}
// Swap 交换索引 i 和 j 处的元素
func (pq GenericPriorityQueue[T]) Swap(i, j int) {
pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}
// Push 将元素 x 添加到队列中
// 注意：这里 x 必须是 T 类型，但接口定义为 any，需要进行类型断言
func (pq *GenericPriorityQueue[T]) Push(x any) {
pq.items = append(pq.items, x.(T))
}
// Pop 移除并返回队列中优先级最高的元素
// 注意：返回值为 any，使用者需要进行类型断言
func (pq *GenericPriorityQueue[T]) Pop() any {
old := pq.items
n := len(old)
item := old[n-1]
pq.items = old[0 : n-1] // 移除最后一个元素
return item
}
// NewGenericPriorityQueue 创建一个新的泛型优先队列
// 参数 less 是一个函数，用于定义元素的优先级（a < b 表示 a 的优先级高于 b）
func NewGenericPriorityQueue[T any](less func(a, b T) bool) *GenericPriorityQueue[T] {
return &GenericPriorityQueue[T]{
items: make([]T, 0),
less: less,
}
}3.3 示例使用（泛型版）
现在，我们可以使用这个泛型优先队列来存储任何类型，只需提供一个合适的比较函数。
func main() {
// 示例1：存储整数，数字越小优先级越高
intPQ := NewGenericPriorityQueue(func(a, b int) bool {
return a < b // 升序，最小的优先级最高
})
heap.Push(intPQ, 3)
heap.Push(intPQ, 1)
heap.Push(intPQ, 4)
heap.Push(intPQ, 2)
fmt.Println("整数优先队列（最小优先）:")
for intPQ.Len() > 0 {
val := heap.Pop(intPQ).(int) // 类型断言
fmt.Printf("%d ", val)
}
fmt.Println("\n---")
// 预期输出: 1 2 3 4
// 示例2：存储自定义结构体，根据 Priority 字段排序
type Task struct {
Name string
Priority int
}
taskPQ := NewGenericPriorityQueue(func(a, b Task) bool {
return a.Priority < b.Priority // Priority 值越小优先级越高
})
heap.Push(taskPQ, Task{Name: "Fix Bug", Priority: 2})
heap.Push(taskPQ, Task{Name: "New Feature", Priority: 1})
heap.Push(taskPQ, Task{Name: "Refactor", Priority: 3})
fmt.Println("任务优先队列（Priority 值越小越优先）:")
for taskPQ.Len() > 0 {
task := heap.Pop(taskPQ).(Task) // 类型断言
fmt.Printf("{Name: %s, Priority: %d} ", task. 
