Go语言中可复用优先级队列的实现：从接口到泛型

type Interface interface {
    sort.Interface // Len, Less, Swap
    Push(x any)    // add x as element Len()
    Pop() any      // remove and return element Len() - 1
}

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap 是一个实现了 heap.Interface 的整数最小堆
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 最小堆：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) {
    // Push 和 Pop 使用指针接收器，因为它们会修改切片的长度
    *h = append(*h, x.(int))
}

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

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
    fmt.Println()
}

package main

import (
    "container/heap"
    "fmt"
)

// PriorityQueue 泛型优先级队列，可以存储任何类型 T
type PriorityQueue[T any] struct {
    items []T
    less  func(a, b T) bool // 自定义比较函数
}

// NewPriorityQueue 构造函数，创建并返回一个泛型优先级队列
func NewPriorityQueue[T any](less func(a, b T) bool) *PriorityQueue[T] {
    return &PriorityQueue[T]{
        items: make([]T, 0),
        less:  less,
    }
}

// 以下方法实现了 heap.Interface 接口
func (pq PriorityQueue[T]) Len() int           { return len(pq.items) }
func (pq PriorityQueue[T]) Less(i, j int) bool { return pq.less(pq.items[i], pq.items[j]) }
func (pq PriorityQueue[T]) Swap(i, j int)      { pq.items[i], pq.items[j] = pq.items[j], pq.items[i] }

func (pq *PriorityQueue[T]) Push(x any) {
    // x 是 any 类型，需要断言回 T
    pq.items = append(pq.items, x.(T))
}

func (pq *PriorityQueue[T]) Pop() any {
    old := pq.items
    n := len(old)
    item := old[n-1]
    pq.items = old[0 : n-1]
    return item
}

func main() {
    // 示例1: 整数最小堆
    fmt.Println("--- 整数最小堆 ---")
    intPQ := NewPriorityQueue(func(a, b int) bool {
        return a < b // 最小堆逻辑
    })
    heap.Push(intPQ, 3)
    heap.Push(intPQ, 1)
    heap.Push(intPQ, 4)
    heap.Push(intPQ, 1)
    heap.Push(intPQ, 5)

    fmt.Printf("堆顶元素 (期望 1): %d\n", heap.Pop(intPQ))
    fmt.Printf("堆顶元素 (期望 1): %d\n", heap.Pop(intPQ))

    for intPQ.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(intPQ))
    }
    fmt.Println("\n")

    // 示例2: 字符串最大堆 (按字典序倒序)
    fmt.Println("--- 字符串最大堆 ---")
    stringPQ := NewPriorityQueue(func(a, b string) bool {
        return a > b // 最大堆逻辑
    })
    heap.Push(stringPQ, "apple")
    heap.Push(stringPQ, "banana")
    heap.Push(stringPQ, "cherry")
    heap.Push(stringPQ, "date")

    fmt.Printf("堆顶元素 (期望 date): %s\n", heap.Pop(stringPQ))

    for stringPQ.Len() > 0 {
        fmt.Printf("%s ", heap.Pop(stringPQ))
    }
    fmt.Println("\n")

    // 示例3: 自定义结构体优先级队列 (按年龄排序)
    type Person struct {
        Name string
        Age  int
    }

    fmt.Println("--- 人员年龄最小堆 ---")
    personPQ := NewPriorityQueue(func(a, b Person) bool {
        return a.Age < b.Age // 按年龄升序
    })
    heap.Push(personPQ, Person{"Alice", 30})
    heap.Push(personPQ, Person{"Bob", 25})
    heap.Push(personPQ, Person{"Charlie", 35})

    fmt.Printf("堆顶元素 (期望 Bob): %+v\n", heap.Pop(personPQ))
    for personPQ.Len() > 0 {
        fmt.Printf("%+v ", heap.Pop(personPQ))
    }
    fmt.Println()
}