heap - 使用容器/堆实现优先级队列

Question

总的来说，我正在尝试使用优先级队列来实现 Dijkstra 算法。

根据 golang-nuts 成员的说法，在 Go 中执行此操作的惯用方法是使用具有自定义底层数据结构的堆接口(interface)。所以我像这样创建了 Node.go 和 PQueue.go:

//Node.go
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
}

和 PQueue.go:

// PQueue.go
package pqueue

import "container/vector"
import "container/heap"

type PQueue struct {
    data vector.Vector
    size int
}

func (pq *PQueue) Init() {
    heap.Init(pq)
}

func (pq *PQueue) IsEmpty() bool {
    return pq.size == 0
}

func (pq *PQueue) Push(i interface{}) {
    heap.Push(pq, i)
    pq.size++
}

func (pq *PQueue) Pop() interface{} {
    pq.size--
    return heap.Pop(pq)
}

func (pq *PQueue) Len() int {
    return pq.size
}

func (pq *PQueue) Less(i, j int) bool {
    I := pq.data.At(i).(Node)
    J := pq.data.At(j).(Node)
    return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}

func (pq *PQueue) Swap(i, j int) {
    temp := pq.data.At(i).(Node)
    pq.data.Set(i, pq.data.At(j).(Node))
    pq.data.Set(j, temp)
}

和 main.go:( Action 在 SolveMatrix 中)

// Euler 81

package main

import "fmt"
import "io/ioutil"
import "strings"
import "strconv"
import "./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++ {
        byrows[row] = (byrows[row])[0 : len(byrows[row])-1]
        bycols := strings.Split(byrows[row], ",", -1)
        for col := 0; col < MATSIZE; col++ {
            matrix[row][col], _ = strconv.Atoi(bycols[col])
        }
    }

    PrintMatrix(matrix)
    sum, len := SolveMatrix(matrix)
    fmt.Printf("len: %d, sum: %d\n", len, 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) {
    var PQ pqueue.PQueue
    var firstNode pqueue.Node
    var endNode pqueue.Node
    msm1 := MATSIZE - 1

    firstNode.Init(0, 0, mat[0][0], 0)
    endNode.Init(msm1, msm1, mat[msm1][msm1], 0)

    if PQ.IsEmpty() { // make compiler stfu about unused variable
        fmt.Print("empty")
    }

    PQ.Push(firstNode) // problem


    return 0, 0
}

问题是，在编译时我收到错误信息:

[~/Code/Euler/81] $ make
6g -o pqueue.6 Node.go PQueue.go
6g main.go
main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument
make: *** [all] Error 1

并且注释掉 PQ.Push(firstNode) 这行确实满足了编译器的要求。但我不明白为什么我一开始会收到错误消息。 Push 不会以任何方式修改参数。

---

更新:为了那些将来在搜索中遇到这个问题的人，上面的代码充满了严重的误解。在下面查看一个更有用的模板:节点Go:

// Node.go
package pqueue

import "fmt"

type Node struct {
    row    int
    col    int
    myVal  int
    sumVal int
    parent *Node
}

func NewNode(r, c, mv, sv int, n *Node) *Node {
    return &Node{r, c, mv, sv, n}
}

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
}

PQueue.go:

// PQueue.go
package pqueue

type PQueue []*Node

func (pq *PQueue) IsEmpty() bool {
    return len(*pq) == 0
}

func (pq *PQueue) Push(i interface{}) {
    a := *pq
    n := len(a)
    a = a[0 : n+1]
    r := i.(*Node)
    a[n] = r
    *pq = a
}

func (pq *PQueue) Pop() interface{} {
    a := *pq
    *pq = a[0 : len(a)-1]
    r := a[len(a)-1]
    return r
}

func (pq *PQueue) Len() int {
    return len(*pq)
}

// post: true iff is i less than j
func (pq *PQueue) Less(i, j int) bool {
    I := (*pq)[i]
    J := (*pq)[j]
    return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}

func (pq *PQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}

func (pq *PQueue) String() string {
    var build string = "{"
    for _, v := range *pq {
        build += v.String()
    }
    build += "}"
    return build
}

Answer 1

package main
var PQ pqueue.PQueue
var firstNode pqueue.Node
PQ.Push(firstNode)

变量 firstNode 是按值传递的，这意味着在函数调用 PQ.Push(firstNode) 中存在参数对参数的隐式赋值。 pqueue.Node 类型包含私有(private)字段，例如 row，这些字段不会从 package pqueue 导出到 package main: “函数参数中 pqueue.Node 的未导出字段‘row’的隐式赋值。”

在Node.go中，将此函数添加到package pqueue:

func NewNode() *Node {
    return &Node{}
}

在PQueue.go中，将此函数添加到package pqueue:

func NewPQueue() *PQueue {
    return &PQueue{}
}

然后。在package main中，你可以这样写:

PQ := pqueue.NewPQueue()
firstNode := pqueue.NewNode()
PQ.Push(firstNode)