Go 泛型优先级队列：实现、对比与实践

type Interface interface {
    // Less 返回此元素是否应该排在元素 x 之前。
    Less(x Interface) bool
    // Index 是优先级队列在将此元素移动到索引 i 时调用的方法。
    Index(i int)
}

type Queue struct {
    h []Interface
}

package main

import (
    "fmt"
    "prio" // 假设 prio 包已在本地定义或通过go mod引入
)

// myInt 实现了 prio.Interface，用于简单的整数优先级队列
type myInt int

func (x myInt) Less(y prio.Interface) bool {
    return x < y.(myInt) // 比较值
}
func (x myInt) Index(i int) {
    // 对于 myInt 这种简单类型，我们可能不需要跟踪索引，但方法必须实现
    // 如果不使用 Remove 操作，此方法可以为空
}

func main() {
    fmt.Println("--- 简单整数优先级队列示例 ---")
    q := prio.New() // 创建一个空队列

    q.Push(myInt(3))
    q.Push(myInt(1))
    q.Push(myInt(4))
    q.Push(myInt(1))
    q.Push(myInt(5))

    fmt.Printf("队列长度: %d\n", q.Len()) // 5
    fmt.Printf("Peek: %v\n", q.Peek())   // 1

    for q.Len() > 0 {
        val := q.Pop()
        fmt.Printf("Pop: %v\n", val) // 1, 1, 3, 4, 5
    }
}

package main

import (
    "fmt"
    "prio" // 假设 prio 包已在本地定义或通过go mod引入
)

// myType 实现了 prio.Interface，并跟踪其在堆中的索引
type myType struct {
    value int
    name  string
    index int // 元素在堆中的索引
}

func (x *myType) Less(y prio.Interface) bool {
    return x.value < y.(*myType).value // 比较值
}

func (x *myType) Index(i int) {
    x.index = i // 更新元素自身的索引
}

func main() {
    fmt.Println("\n--- 带有索引管理的优先级队列示例 ---")
    q := prio.New()

    // 创建并添加元素，同时保存对它们的引用以便后续操作
    e1 := &myType{value: 30, name: "Task C"}
    e2 := &myType{value: 10, name: "Task A"}
    e3 := &myType{value: 40, name: "Task D"}
    e4 := &myType{value: 20, name: "Task B"}

    q.Push(e1)
    q.Push(e2)
    q.Push(e3)
    q.Push(e4)

    fmt.Printf("队列长度: %d\n", q.Len()) // 4
    fmt.Printf("Peek: %v (index: %d)\n", q.Peek().(*myType), q.Peek().(*myType).index) // Task A (index: 0)

    // 假设我们想移除 Task C (e1)，需要知道它的当前索引
    fmt.Printf("移除 Task C (当前索引: %d)\n", e1.index)
    removed := q.Remove(e1.index).(*myType)
    fmt.Printf("已移除: %v\n", removed)
    fmt.Printf("移除后队列长度: %d\n", q.Len()) // 3

    fmt.Println("移除后队列元素:")
    for q.Len() > 0 {
        val := q.Pop().(*myType)
        fmt.Printf("Pop: %v (index: %d)\n", val, val.index)
    }
    // 预期输出: Task B, Task D
}

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

import (
    "container/heap"
    "fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 最小堆
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h) // 初始化堆
    heap.Push(h, 3)
    fmt.Printf("最小元素: %d\n", (*h)[0]) // 1
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h)) // 1 2 3 5
    }
}