使用Go语言实现优先级队列：基于container/heap的实践指南

// pqueue/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, p *Node) *Node {
    return &Node{r, c, mv, sv, p}
}

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

// String 返回节点的字符串表示
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 *Node) 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/pqueue.go
package pqueue

import "container/heap" // 引入 container/heap 包

// PQueue 是一个 []*Node 类型的别名，它将作为堆的底层数据结构。
// PQueue 实现了 heap.Interface 接口。
type PQueue []*Node

// Len 返回堆中元素的数量。
func (pq PQueue) Len() int {
    return len(pq)
}

// Less 比较两个节点的优先级。
// 这里以 (sumVal + myVal) 的和作为优先级，值越小优先级越高。
func (pq PQueue) Less(i, j int) bool {
    // 注意：这里直接访问了 Node 的未导出字段 sumVal 和 myVal。
    // 这是因为 PQueue 和 Node 都在同一个 pqueue 包中。
    return (pq[i].sumVal + pq[i].myVal) < (pq[j].sumVal + pq[j].myVal)
}

// Swap 交换堆中两个元素的位置。
func (pq PQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

// Push 向堆中添加一个元素。
// 这个方法由 heap.Push 调用。
func (pq *PQueue) Push(x interface{}) {
    // 类型断言，确保 x 是 *Node 类型
    *pq = append(*pq, x.(*Node))
}

// Pop 从堆中移除并返回优先级最高的元素。
// 这个方法由 heap.Pop 调用。
func (pq *PQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1] // 获取最后一个元素
    *pq = old[0 : n-1] // 截断切片，移除最后一个元素
    return item
}

// NewPQueue 是 PQueue 的构造函数，返回一个已初始化为堆的 PQueue 指针。
func NewPQueue() *PQueue {
    pq := make(PQueue, 0) // 创建一个空的 PQueue 切片
    heap.Init(&pq)        // 对切片进行堆初始化
    return &pq
}

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

// String 返回优先级队列的字符串表示。
func (pq *PQueue) String() string {
    var build string = "{"
    for _, v := range *pq {
        build += v.String()
    }
    build += "}"
    return build
}

// main.go
package main

import (
    "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") // 修正 Split 参数
    if len(byrows) > MATSIZE { // 处理文件末尾空行
        byrows = byrows[:MATSIZE]
    }

    for row := 0; row < MATSIZE; row++ {
        // 移除行末的可能的空白字符或回车符
        byrows[row] = strings.TrimSpace(byrows[row])
        if len(byrows[row]) == 0 {
            continue // 跳过空行
        }
        bycols := strings.Split(byrows[row], ",")
        for col := 0; col < MATSIZE; col++ {
            matrix[row][col], _ = strconv.Atoi(bycols[col])
        }
    }

    PrintMatrix(matrix)
    sum, length := SolveMatrix(matrix) // 修改变量名 len 为 length，避免与内置函数冲突
    fmt.Printf("length: %d, sum: %d\n", length, sum)
}

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

func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
    // 使用 NewPQueue 构造函数创建优先级队列实例
    PQ := pqueue.NewPQueue()

    // 使用 NewNode 构造函数创建 Node 实例，并得到其指针
    firstNode := pqueue.NewNode(0, 0, mat[0][0], 0, nil)
    // endNode := pqueue.NewNode(MATSIZE-1, MATSIZE-1, mat[MATSIZE-1][MATSIZE-1], 0, nil) // 未使用

    // 检查优先级队列是否为空
    if PQ.IsEmpty() {
        fmt.Println("Priority Queue is empty initially.")
    }

    // 将 firstNode (一个 *pqueue.Node) 推入优先级队列
    // heap.Push 接受一个 heap.Interface 类型和一个 interface{} 类型的元素
    heap.Push(PQ, firstNode) // 正确的用法：直接调用 heap.Push

    fmt.Printf("After pushing firstNode, PQ: %s\n", PQ.String())

    // 示例：从队列中取出元素
    if !PQ.IsEmpty() {
        poppedNode := heap.Pop(PQ).(*pqueue.Node) // heap.Pop 返回 interface{}，需要类型断言
        fmt.Printf("Popped node: %s\n", poppedNode.String())
    }

    return 0, 0
}