Go语言中优先队列的实现策略：理解container/heap与类型特定化

package main

import (
    "container/heap"
    "fmt"
)

// Task 定义了任务结构体，包含名称和优先级
type Task struct {
    Name     string
    Priority int // 优先级值越小，优先级越高
    Index    int // 任务在堆中的索引，用于更新
}

// PriorityQueue 实现了 heap.Interface 接口
type PriorityQueue []*Task

// Len 返回队列中的元素数量
func (pq PriorityQueue) Len() int { return len(pq) }

// Less 定义了元素的比较规则。这里实现的是一个最小堆，
// 优先级值越小（即数值越小），优先级越高，越先被取出。
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 any) {
    n := len(*pq)
    item := x.(*Task) // 类型断言
    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 修改堆中某个元素的优先级
func (pq *PriorityQueue) Update(task *Task, name string, priority int) {
    task.Name = name
    task.Priority = priority
    heap.Fix(pq, task.Index) // 重新调整堆结构
}

func main() {
    tasks := map[string]*Task{
        "Task A": {Name: "Task A", Priority: 3},
        "Task B": {Name: "Task B", Priority: 1},
        "Task C": {Name: "Task C", Priority: 4},
        "Task D": {Name: "Task D", Priority: 2},
    }

    pq := make(PriorityQueue, 0, len(tasks)) // 初始化一个空的优先队列
    heap.Init(&pq)                          // 初始化堆

    // 将任务推入优先队列
    for _, task := range tasks {
        heap.Push(&pq, task)
    }

    fmt.Println("初始任务队列:")
    for pq.Len() > 0 {
        task := heap.Pop(&pq).(*Task)
        fmt.Printf("处理任务: %s (优先级: %d)\n", task.Name, task.Priority)
    }

    fmt.Println("\n--- 带有更新操作的示例 ---")
    // 重新填充队列
    for _, task := range tasks {
        heap.Push(&pq, task)
    }

    // 模拟更新一个任务的优先级
    fmt.Println("更新 Task C 的优先级为 0 (最高优先级)")
    pq.Update(tasks["Task C"], "Task C", 0)

    fmt.Println("更新后任务队列:")
    for pq.Len() > 0 {
        task := heap.Pop(&pq).(*Task)
        fmt.Printf("处理任务: %s (优先级: %d)\n", task.Name, task.Priority)
    }
}

// 泛型版本的LessFunc，可以传入自定义比较函数
type GenericPriorityQueue[T any] struct {
    items []T
    less  func(a, b T) bool
}

func (gpq GenericPriorityQueue[T]) Len() int           { return len(gpq.items) }
func (gpq GenericPriorityQueue[T]) Less(i, j int) bool { return gpq.less(gpq.items[i], gpq.items[j]) }
func (gpq GenericPriorityQueue[T]) Swap(i, j int)      { gpq.items[i], gpq.items[j] = gpq.items[j], gpq.items[i] }
func (gpq *GenericPriorityQueue[T]) Push(x any)        { gpq.items = append(gpq.items, x.(T)) }
func (gpq *GenericPriorityQueue[T]) Pop() any {
    old := gpq.items
    n := len(old)
    item := old[n-1]
    gpq.items = old[0 : n-1]
    return item
}

// NewGenericPriorityQueue 创建一个泛型优先队列
func NewGenericPriorityQueue[T any](less func(a, b T) bool) *GenericPriorityQueue[T] {
    gpq := &GenericPriorityQueue[T]{
        items: make([]T, 0),
        less:  less,
    }
    // heap.Init(gpq) // 如果需要初始化一个非空队列
    return gpq
}

// 实际使用时
// pq := NewGenericPriorityQueue(func(a, b *Task) bool { return a.Priority < b.Priority })
// heap.Push(pq, &Task{...})