Go语言优先队列实现：从特定类型到泛型复用策略

package heap

import "sort"

type Interface interface {
    sort.Interface // 包含 Len(), Less(i, j int), Swap(i, j int)
    Push(x any)    // 将 x 添加到堆中
    Pop() any      // 移除并返回堆顶元素
}

package main

import (
    "container/heap"
    "fmt"
)

// Item 表示优先队列中的一个元素
type Item struct {
    Value    string // 元素值
    Priority int    // 优先级，数字越小优先级越高
    Index    int    // 在堆中的索引，用于更新（可选，但对于 Update 操作很有用）
}

// PriorityQueue 实现了 heap.Interface 接口，是一个 Item 指针的切片
type PriorityQueue []*Item

// 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) // 重新调整堆结构以保持堆属性
}

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
}

package main

import (
    "container/heap"
    "fmt"
)

// GenericPriorityQueue 实现了 heap.Interface 接口，可用于任何类型 T，
// 只要提供了正确的比较函数。
type GenericPriorityQueue[T any] struct {
    items []T
    less  func(a, b T) bool // 比较函数，定义优先级
}

// 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,
    }
}

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.