Go 语言中基于 container/heap 实现优先队列的专业指南

// Node.go
package pqueue

import "fmt"

// Node 代表优先队列中的一个元素
type Node struct {
    row    int // 行坐标，未导出
    col    int // 列坐标，未导出
    myVal  int // 节点自身的值，未导出
    sumVal int // 从起点到当前节点的累积和，未导出
    parent *Node // 父节点指针，用于路径回溯，未导出
}

// NewNode 是 Node 的构造函数，返回一个 Node 指针
// 建议使用构造函数来初始化结构体，尤其当结构体包含未导出字段时
func NewNode(r, c, mv, sv int, n *Node) *Node {
    return &Node{r, c, mv, sv, n}
}

// Eq 检查两个 Node 是否相等（基于行和列坐标）
func (n *Node) Eq(o *Node) bool {
    return n.row == o.row && n.col == o.col
}

// String 方法用于 Node 的字符串表示
func (n *Node) String() string {
    return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal)
}

// 以下是 Node 字段的访问器和修改器，如果需要从外部包访问未导出字段，则必须提供
func (n *Node) Row() int {
    return n.row
}

func (n *nNode) Col() int {
    return n.col
}

func (n *Node) SetParent(p *Node) {
    n.parent = p
}

func (n *Node) Parent() *Node {
    return n.parent
}

func (n *Node) MyVal() int {
    return n.myVal
}

func (n *Node) SumVal() int {
    return n.sumVal
}

func (n *Node) SetSumVal(sv int) {
    n.sumVal = sv
}

// PQueue.go
package pqueue

import "container/heap" // 导入 heap 包

// PQueue 是一个基于 []*Node 的优先队列，它实现了 heap.Interface
type PQueue []*Node

// NewPQueue 是 PQueue 的构造函数，返回一个 PQueue 指针
func NewPQueue() *PQueue {
    pq := make(PQueue, 0) // 初始化一个空的 PQueue 切片
    // heap.Init(&pq) // 对于新创建的空堆，通常不需要显式调用 Init
    return &pq
}

// IsEmpty 检查优先队列是否为空
func (pq *PQueue) IsEmpty() bool {
    return len(*pq) == 0
}

// Len 返回优先队列中的元素数量
// 这是 heap.Interface 的一部分
func (pq *PQueue) Len() int {
    return len(*pq)
}

// Less 比较索引 i 和 j 处的元素优先级
// 这是 heap.Interface 的一部分，决定了堆的类型（最小堆或最大堆）
// 此处实现的是最小堆，即 (I.sumVal + I.myVal) 越小优先级越高
func (pq *PQueue) Less(i, j int) bool {
    I := (*pq)[i]
    J := (*pq)[j]
    return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}

// Swap 交换索引 i 和 j 处的元素
// 这是 heap.Interface 的一部分
func (pq *PQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}

// Push 将元素 x 添加到优先队列中
// 这是 heap.Interface 的一部分，它仅负责将元素添加到底层切片的末尾
// 堆的重新平衡由 container/heap.Push 函数完成
func (pq *PQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Node))
}

// Pop 从优先队列中移除并返回最后一个元素
// 这是 heap.Interface 的一部分，它仅负责从底层切片中移除最后一个元素
// 堆的重新平衡和根元素的移除由 container/heap.Pop 函数完成
func (pq *PQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1] // 获取最后一个元素
    *pq = old[0 : n-1] // 移除最后一个元素
    return x
}

// String 方法用于 PQueue 的字符串表示
func (pq *PQueue) String() string {
    var build string = "{"
    for _, v := range *pq {
        build += v.String()
    }
    build += "}"
    return build
}

// main.go
package main

import (
    "container/heap" // 导入 Go 标准库的 heap 包
    "fmt"
    "io/ioutil"
    "strconv"
    "strings"
    "./pqueue" // 导入自定义的 pqueue 包
)

const MATSIZE = 5
const MATNAME = "matrix_small.txt"

func main() {
    // 示例：读取矩阵数据（与原问题保持一致，但非核心）
    var matrix [MATSIZE][MATSIZE]int
    contents, err := ioutil.ReadFile(MATNAME)
    if err != nil {
        panic("FILE IO ERROR!")
    }
    inFileStr := string(contents)
    byrows := strings.Split(inFileStr, "\n", -1)

    for row := 0; row < MATSIZE; row++ {
        // 移除每行末尾的 '\r' 或其他空白字符
        byrows[row] = strings.TrimSpace(byrows[row])
        if len(byrows[row]) == 0 {
            continue // 跳过空行
        }
        bycols := strings.Split(byrows[row], ",", -1)
        for col := 0; col < MATSIZE; col++ {
            matrix[row][col], _ = strconv.Atoi(bycols[col])
        }
    }

    PrintMatrix(matrix)

    // 使用优先队列解决问题（Dijkstra 简化示例）
    sum, length := SolveMatrix(matrix)
    fmt.Printf("Path length: %d, Total sum: %d\n", length, sum)
}

// PrintMatrix 打印矩阵
func PrintMatrix(mat [MATSIZE][MATSIZE]int) {
    fmt.Println("Matrix:")
    for r := 0; r < MATSIZE; r++ {
        for c := 0; c < MATSIZE; c++ {
            fmt.Printf("%d ", mat[r][c])
        }
        fmt.Print("\n")
    }
}

// SolveMatrix 示例：使用优先队列寻找路径
func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
    // 1. 创建一个 PQueue 实例
    pq := pqueue.NewPQueue() // 使用构造函数获取 PQueue 指针

    // 2. 初始化堆
    // 对于一个空的 PQueue，通常不需要显式调用 heap.Init。
    // 如果是从一个已存在的切片构建堆，则需要调用。
    heap.Init(pq) // pq 是一个 *pqueue.PQueue 类型，满足 heap.Interface

    // 3. 创建并添加第一个节点
    firstNode := pqueue.NewNode(0, 0, mat[0][0], 0, nil) // 使用构造函数获取 Node 指针
    heap.Push(pq, firstNode) // 使用 container/heap 包的 Push 函数

    fmt.Printf("Initial PQueue: %s\n", pq.String()) // 打印队列内容

    // 示例：从队列中取出元素
    if !pq.IsEmpty() {
        poppedNode := heap.Pop(pq).(*pqueue.Node) // 使用 container/heap 包的 Pop 函数
        fmt.Printf("Popped node: %s\n", poppedNode.String())
    }

    // 模拟更多操作，例如 Dijkstra 算法的循环
    // while pq is not empty:
    //     current = heap.Pop(pq)
    //     explore neighbors
    //     if new path is better:
    //         update neighbor's sumVal
    //         heap.Push(pq, neighbor) // Or update in place and fix heap using heap.Fix

    // 示例返回占位符
    return 0, 0
}