Go语言中实现可重用优先级队列的策略与实践

package main

import (
    "container/heap"
    "fmt"
)

// Item 表示优先级队列中的一个元素
type Item struct {
    value    string // 元素的值
    priority int    // 元素的优先级 (数字越小优先级越高)
    index    int    // 元素在堆切片中的索引，用于高效更新
}

// PriorityQueue 实现了 heap.Interface 接口，并持有一组 Item
type PriorityQueue []*Item

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
}

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.(*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 // 元素已不在堆中，索引设为-1
    *pq = old[0 : n-1]
    return item
}

// update 修改队列中元素的优先级和值
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index) // 调用 heap.Fix 重新调整堆结构
}

func main() {
    // 一些待加入队列的元素及其优先级
    items := map[string]int{
        "banana": 3, "apple": 2, "pear": 4, "grape": 1,
    }

    // 创建一个优先级队列，并初始化
    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) // 初始化堆，使其满足堆属性

    fmt.Println("初始队列元素 (按优先级从高到低弹出):")
    // 依次从队列中取出元素，它们将按优先级顺序弹出
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item) // 使用 heap.Pop 弹出元素
        fmt.Printf("%s: %d\n", item.value, item.priority)
    }

    fmt.Println("\n演示更新和添加新元素:")
    // 创建一个新的空队列
    pq2 := make(PriorityQueue, 0)
    heap.Init(&pq2) // 初始化空堆

    item1 := &Item{value: "orange", priority: 5}
    item2 := &Item{value: "kiwi", priority: 0}
    item3 := &Item{value: "mango", priority: 7}

    heap.Push(&pq2, item1) // 使用 heap.Push 添加元素
    heap.Push(&pq2, item2)
    heap.Push(&pq2, item3)

    fmt.Println("更新前队列顶部元素 (优先级最高):")
    if pq2.Len() > 0 {
        fmt.Printf("顶部元素: %s: %d\n", pq2[0].value, pq2[0].priority)
    }

    // 更新 item1 的优先级
    fmt.Println("将 'orange' 的优先级从 5 更新为 1...")
    pq2.update(item1, item1.value, 1) // 调用自定义的 update 方法

    fmt.Println("更新后队列元素 (按优先级从高到低弹出):")
    for pq2.Len() > 0 {
        item := heap.Pop(&pq2).(*Item)
        fmt.Printf("%s: %d\n", item.value, item.priority)
    }
}

初始队列元素 (按优先级从高到低弹出):
grape: 1
apple: 2
banana: 3
pear: 4

演示更新和添加新元素:
更新前队列顶部元素 (优先级最高):
顶部元素: kiwi: 0
将 'orange' 的优先级从 5 更新为 1...
更新后队列元素 (按优先级从高到低弹出):
kiwi: 0
orange: 1
mango: 7