Go语言中利用container/heap接口实现优先级队列的实践指南

package pqueue

type Node struct {
    row    int // 未导出字段
    col    int // 未导出字段
    myVal  int // 未导出字段
    sumVal int // 未导出字段
}

func (n *Node) Init(r, c, mv, sv int) {
    n.row = r
    n.col = c
    n.myVal = mv
    n.sumVal = sv
}

func (n *Node) Equals(o *Node) bool {
    return n.row == o.row && n.col == o.col
}

package pqueue

import "container/heap"
// import "container/vector" // 此包已废弃，不推荐使用

type PQueue struct {
    // data vector.Vector // 已废弃，不推荐
    // 实际应为切片，例如 []interface{} 或 []*Node
    size int // 此字段在实际heap.Interface实现中通常不必要，len()方法即可
}

// 这里的Push和Pop方法是错误的，因为它们直接调用了heap包的函数，
// 而heap.Interface要求的是类型自身实现Push/Pop方法
func (pq *PQueue) Push(i interface{}) {
    heap.Push(pq, i) // 错误：heap.Push的第一个参数应为heap.Interface类型实例
    pq.size++
}

func (pq *PQueue) Pop() interface{} {
    pq.size--
    return heap.Pop(pq) // 错误：heap.Pop的参数应为heap.Interface类型实例
}

// ... Len, Less, Swap 方法省略，但它们需要正确访问底层数据

// main.go (初始尝试)
package main

import "./pqueue" // 导入自定义的pqueue包

func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
    var PQ pqueue.PQueue
    var firstNode pqueue.Node // 声明Node类型的值

    // ... firstNode.Init(...)

    PQ.Push(firstNode) // 编译错误发生在此处
    return 0, 0
}

main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument

// Node.go (修正版)
package pqueue

import "fmt"

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} // 返回Node的指针
}

// 以下是Node的导出方法，用于访问和修改未导出字段
func (n *Node) Eq(o *Node) bool {
    return n.row == o.row && n.col == o.col
}

func (n *Node) String() string {
    return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal)
}

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
}

type Interface interface {
    sort.Interface // 包含 Len(), Less(i, j int), Swap(i, j int)
    Push(x interface{})
    Pop() interface{}
}

// PQueue.go (修正版)
package pqueue

import "fmt" // 用于String方法

// PQueue 是一个 []*Node 类型的别名，直接作为底层数据结构
type PQueue []*Node

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

// Push 方法将元素 x 添加到队列中。
// 注意：此方法仅处理底层切片的增长，不负责维护堆属性。
// 堆属性的维护由 container/heap 包的 heap.Push 函数完成。
func (pq *PQueue) Push(x interface{}) {
    // 将 interface{} 类型断言为 *Node
    node := x.(*Node)
    *pq = append(*pq, node) // 将节点添加到切片末尾
}

// Pop 方法从队列中移除并返回最后一个元素。
// 注意：此方法仅处理底层切片的缩减，不负责维护堆属性。
// 堆属性的维护由 container/heap 包的 heap.Pop 函数完成。
func (pq *PQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    node := old[n-1] // 获取最后一个元素
    *pq = old[0 : n-1] // 截断切片，移除最后一个元素
    return node // 返回移除的元素
}

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

// Less 比较索引 i 和 j 处的元素，返回 i 是否小于 j。
// 这是优先级队列的核心逻辑，决定了元素的排序方式。
func (pq *PQueue) Less(i, j int) bool {
    // 优先级逻辑：(I.sumVal + I.myVal) 越小优先级越高
    return ((*pq)[i].sumVal + (*pq)[i].myVal) < ((*pq)[j].sumVal + (*pq)[j].myVal)
}

// Swap 交换索引 i 和 j 处的元素
func (pq *PQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}

// 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 (
    "fmt"
    "io/ioutil"
    "strconv"
    "strings"
    "container/heap" // 导入container/heap包
    "./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++ {
        // 假设每行末尾有不必要的字符，例如回车符，需要去除
        if len(byrows[row]) > 0 && byrows[row][len(byrows