Golang heap实现优先级队列教程

在Go语言中使用container/heap实现优先级队列需定义结构体并实现heap.Interface的五个方法。1. 定义包含优先级字段的Item结构体和基于切片的PriorityQueue；2. 实现Len、Less、Swap用于堆排序逻辑；3. Push和Pop方法负责添加和移除元素，需使用指针接收者；4. 通过heap.Init初始化堆结构；5. 使用heap.Push和heap.Pop操作队列，注意类型断言及保持堆特性。

在 Go 语言中，container/heap 包提供了一个堆操作的接口，非常适合用来实现优先级队列。但这个包本身并不直接提供“队列”结构，而是需要我们自己定义数据结构并实现 heap.Interface 接口。下面我们就一步步来看看如何用它来实现一个自定义的优先级队列。

实现优先级队列的关键步骤

要使用 container/heap 来构建优先级队列，核心是定义一个自己的结构体，并让它满足 heap.Interface 的五个方法：Len, Less, Swap, Push, Pop。

通常我们会选择一个结构体切片作为底层存储，每个元素包含优先级字段（比如 priority int），然后根据该字段决定堆的排序方式。

定义结构体和实现接口方法

假设我们要实现一个按优先级从高到低排列的队列（数值越大优先级越高），可以这样写：

type Item struct {
    value    string // 队列中的实际数据
    priority int    // 优先级
}

type PriorityQueue []*Item

接下来实现接口方法：

• Len() 和 Swap() 比较简单，就是对切片的操作。
• Less(i, j int) bool 是关键，决定了堆的顺序。如果是最大堆，就返回 pq[i].priority > pq[j].priority。
• Push 和 Pop 用于向堆中添加或取出元素。

示例代码如下：

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

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

注意：Push 和 Pop 方法必须是指针接收者，因为它们会修改队列内容。

初始化和使用堆结构

初始化时要用 heap.Init 来将你的结构体转换为一个合法的堆：

items := []*Item{
    {"A", 3},
    {"B", 1},
    {"C", 2},
}

pq := PriorityQueue(items)
heap.Init(&pq)

// 添加新元素
heap.Push(&pq, &Item{"D", 5})

// 取出元素
for pq.Len() > 0 {
    item := heap.Pop(&pq).(*Item)
    fmt.Println(item.value, item.priority)
}

输出结果会按照优先级从高到低依次打印：

D 5
A 3
C 2
B 1

注意事项与常见问题

• heap.Pop 返回的是 interface{}，记得做类型断言。
• 如果你希望最小堆，只需要把 Less 改成 < 即可。
• 自定义结构体时，不要忘记实现全部五个接口方法。
• 所有操作都应通过 heap 包的方法进行，直接修改底层切片可能导致堆结构破坏。

基本上就这些。虽然看起来有点模板化，但只要理解了接口的作用，每次复制粘贴改改字段就能用了。