Go语言container/heap包：优先级队列的正确实现与常见陷阱

type Interface interface {
    sort.Interface // Len, Less, Swap
    Push(x any)    // add x as element Len()
    Pop() any      // remove and return element Len() - 1.
}

// Item 结构体表示优先级队列中的一个元素
type Item struct {
    container interface{} // 存储实际数据
    priority  int         // 元素的优先级
    index     int         // 元素在堆中的索引，用于更新优先级（可选）
}

// PriorityQueue 是一个 Item 指针的切片，代表我们的优先级队列
type PriorityQueue []*Item

// NewItem 辅助函数，用于创建新的 Item
func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

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]
    pq[i].index = i // 更新元素的索引
    pq[j].index = j // 更新元素的索引
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n // 记录元素在堆中的索引
    *pq = append(*pq, item) // 必须对指针指向的底层切片进行操作
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1] // 取出最后一个元素
    old[n-1] = nil   // 避免内存泄漏
    item.index = -1  // 标记元素已不在堆中
    *pq = old[0 : n-1] // 缩短切片长度
    return item.container // 返回实际数据
}

package main

import (
    "container/heap"
    "fmt"
)

// Item, PriorityQueue, NewItem, Len, Less, Swap, Push, Pop 的定义如上所示

func main() {
    // 1. 初始化优先级队列：必须使用 new() 或 &{} 获取其指针
    q := new(PriorityQueue) // 或者 q := &PriorityQueue{}

    // 2. 初始化堆：传入队列的指针
    heap.Init(q)

    fmt.Printf("队列初始化后的地址: %p\n", q) // 打印队列的地址

    // 3. 向队列中推入元素
    // 注意：这里的 q 已经是 PriorityQueue 的指针类型
    heap.Push(q, NewItem("任务H", 2))

    for i := 0; i < 5; i++ {
        item := NewItem(fmt.Sprintf("任务%d", i), i*13%7)
        heap.Push(q, item)
    }

    fmt.Println("\n从队列中取出元素 (优先级从高到低):")
    // 4. 从队列中取出元素，直到队列为空
    for q.Len() > 0 {
        // heap.Pop 返回的是 interface{} 类型，需要类型断言
        itemContent := heap.Pop(q).(string)
        fmt.Printf("取出: %s\n", itemContent)
    }
}

package main

import (
    "container/heap"
    "fmt"
)

// Item 结构体表示优先级队列中的一个元素
type Item struct {
    container interface{} // 存储实际数据
    priority  int         // 元素的优先级
    index     int         // 元素在堆中的索引，用于更新优先级（可选）
}

// PriorityQueue 是一个 Item 指针的切片，代表我们的优先级队列
type PriorityQueue []*Item

// NewItem 辅助函数，用于创建新的 Item
func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

// 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 交换队列中两个索引位置的元素
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i // 更新元素的索引
    pq[j].index = j // 更新元素的索引
}

// Push 将一个元素添加到队列中
// 必须使用指针接收器，因为会修改底层切片的长度和容量
func (pq *PriorityQueue) Push(x interface{}) {
    // fmt.Printf("Push方法内队列地址: %p\n", pq) // 调试用
    n := len(*pq)
    item := x.(*Item)
    item.index = n // 记录元素在堆中的索引
    *pq = append(*pq, item) // 对指针指向的底层切片进行操作
}

// Pop 从队列中移除并返回优先级最高的元素
// 必须使用指针接收器，因为会修改底层切片的长度
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1] // 取出最后一个元素
    old[n-1] = nil   // 避免内存泄漏，帮助GC
    item.index = -1  // 标记元素已不在堆中
    *pq = old[0 : n-1] // 缩短切片长度
    return item.container // 返回实际数据
}

func main() {
    // 初始化优先级队列：必须使用 new() 或 &{} 获取其指针
    q := new(PriorityQueue) // q 是一个 *PriorityQueue 类型

    // 初始化堆：传入队列的指针
    heap.Init(q)

    fmt.Printf("主函数中队列变量 q 的地址: %p\n", q)

    // 向队列中推入元素
    heap.Push(q, NewItem("任务H", 2))

    for i := 0; i < 5; i++ {
        item := NewItem(fmt.Sprintf("任务%d", i), i*13%7)
        heap.Push(q, item)
    }

    fmt.Println("\n从队列中取出元素 (优先级从高到低):")
    // 从队列中取出元素，直到队列为空
    for q.Len() > 0 {
        // heap.Pop 返回的是 interface{} 类型，需要类型断言
        itemContent := heap.Pop(q).(string)
        fmt.Printf("取出: %s\n", itemContent)
    }
}