Go语言中基于container/heap实现优先队列：原理与实践

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

// 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)
}

// 提供导出方法来访问非导出字段
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.go
package pqueue

// PQueue 是一个基于Node指针切片的优先队列类型
type PQueue []*Node

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

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

// Less 实现了heap.Interface的Less方法，定义了元素的优先级比较规则
// 这里以(sumVal + 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 实现了heap.Interface的Swap方法，交换两个元素的位置
func (pq *PQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}

// Push 实现了heap.Interface的Push方法，将元素x添加到切片末尾
// 注意：此方法仅负责将元素追加到切片，不执行堆的“上浮”操作
func (pq *PQueue) Push(x interface{}) {
    // 类型断言，确保x是*Node类型
    node := x.(*Node)
    *pq = append(*pq, node)
}

// Pop 实现了heap.Interface的Pop方法，从切片末尾移除并返回元素
// 注意：此方法仅负责从切片移除元素，不执行堆的“下沉”操作
func (pq *PQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    node := old[n-1] // 获取最后一个元素
    *pq = old[0 : n-1] // 截断切片，移除最后一个元素
    return node // 返回被移除的元素
}

// 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" // 假设存在一个这样的文件，例如：
/*
131,673,234,103,18
201,96,342,965,150
630,803,746,422,111
537,699,497,121,956
805,732,524,37,331
*/

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参数，Split不再需要
    // 过滤空行，尤其是在文件末尾有换行符时
    var filteredRows []string
    for _, row := range byrows {
        if len(strings.TrimSpace(row)) > 0 {
            filteredRows = append(filteredRows, row)
        }
    }

    for row := 0; row < MATSIZE; row++ {
        // 移除行末的潜在回车符或空格
        bycols := strings.Split(strings.TrimSpace(filteredRows[row]), ",")
        for col := 0; col < MATSIZE; col++ {
            matrix[row][col], _ = strconv.Atoi(bycols[col])
        }
    }

    PrintMatrix(matrix)
    sum, length := SolveMatrix(matrix)
    fmt.Printf("Path length: %d, Total sum: %d\n", length, sum)
}

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

func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
    // 正确初始化PQueue，它是一个切片，初始为空
    pq := make(pqueue.PQueue, 0)
    // 使用heap.Init对切片进行初始化（可选，如果初始为空，Push会自动维护堆属性）
    heap.Init(&pq)

    // 创建第一个节点，使用NewNode构造函数返回指针
    firstNode := pqueue.NewNode(0, 0, mat[0][0], 0, nil)
    firstNode.SetSumVal(mat[0][0]) // 起点累计值就是自身值

    // 将第一个节点推入优先队列
    heap.Push(&pq, firstNode) // 正确地将*PQueue和*Node传递给heap.Push

    // 示例：从队列中弹出元素并打印
    if pq.Len() > 0 {
        poppedNode := heap.Pop(&pq).(*pqueue.Node)
        fmt.Printf("Popped node: %s\n", poppedNode.String())
    }

    // 实际的Dijkstra算法逻辑会在这里展开，例如：
    // var visited map[string]bool // 用于记录已访问节点
    // ... 循环直到找到目标节点或队列为空 ...
    // current := heap.Pop(&pq).(*pqueue.Node)
    // ... 探索邻居节点，计算新的sumVal，创建新的Node并Push到pq ...

    // 简化示例，返回0,0
    return 0, 0
}