Go语言中实现优先级队列：container/heap包的正确姿势

type Interface interface {
    sort.Interface // Len, Less, Swap
    Push(x interface{})
    Pop() interface{}
}

package pq

import "fmt" // 仅用于调试输出

// Item 表示优先级队列中的一个元素
type Item struct {
    container interface{} // 元素实际存储的值
    priority  int         // 元素的优先级
    index     int         // 元素在堆中的索引，用于更新优先级
}

// NewItem 创建一个新的 Item 实例
func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

// PriorityQueue 是实现 heap.Interface 的切片类型
type PriorityQueue []*Item

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

// Less 实现了最大堆，如果 pq[i] 的优先级高于 pq[j]，则返回 true
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
}

func (pq *PriorityQueue) Push(x interface{}) {
    // 调试输出，观察地址变化
    // fmt.Printf("Push method receiver adr: %p\n", pq)

    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] // 取出最后一个元素
    item.index = -1  // 将元素的索引设置为无效值
    *pq = old[0 : n-1] // 截断切片，移除最后一个元素
    return item.container // 返回被移除元素的值
}

package main

import (
    "container/heap"
    "fmt"
    "math/rand"
    "time"
)

// Item, NewItem, PriorityQueue, Len, Less, Swap, Push, Pop 的定义同上文
// 为了代码完整性，这里再次包含它们的定义
type Item struct {
    container interface{}
    priority  int
    index     int
}

func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

type PriorityQueue []*Item

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]
    item.index = -1
    *pq = old[0 : n-1]
    return item.container
}

func main() {
    // 1. 初始化优先级队列：声明一个 PriorityQueue 的指针
    // q := pq.PriorityQueue{} // 错误：这是值类型，需要传递其地址给 heap 函数
    q := new(PriorityQueue) // 正确：直接创建一个 PriorityQueue 的指针

    // 2. 初始化堆：将 PriorityQueue 的指针传递给 heap.Init
    heap.Init(q) // 注意这里传递的是 q (一个指针)

    fmt.Printf("Initial Queue Address: %p\n", q)

    // 3. 插入初始元素
    heap.Push(q, NewItem("Initial Item", 100)) // 注意这里传递的是 q (一个指针)

    // 4. 插入随机元素
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < 5; i++ {
        priority := rand.Intn(100) // 0-99 之间的随机优先级
        item := NewItem(fmt.Sprintf("Test Item %d", i+1), priority)
        heap.Push(q, item) // 注意这里传递的是 q (一个指针)
    }

    fmt.Println("\nPopping elements from the priority queue (highest priority first):")
    // 5. 弹出元素直到队列为空
    for q.Len() > 0 {
        // 注意这里传递的是 q (一个指针)
        poppedItemValue := heap.Pop(q).(string)
        fmt.Printf("Popped: %s\n", poppedItemValue)
    }
}