优先队列和堆

Question

I'm trying to implement a priority queue based on the example provided in the documentation. Docs: priorityQueue

In short it looks like this (not everything is included):

    package pq

    type Item struct {
        container interface{}
        priority  int
        index     int
    }

    type PriorityQueue []*Item

    func NewItem(value interface{}, prio int) *Item {
        return &Item {container: value, priority: prio}
    }

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq *PriorityQueue) Swap(i, j int) {
    (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
    (*pq)[i].index = i
    (*pq)[j].index = j
}

    func (pq PriorityQueue) Push(x interface{}) {
        fmt.Printf("adr: %p
", &pq)
        n := len(pq)
        item := x.(*Item)
        item.index = n
        pq = append(pq, item)
    }

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    itm := old[n - 1]
    itm.index = -1
    *pq = old[0 : n-1]
    return itm.container
}

The main.go file:

func main() {
    q := pq.PriorityQueue{}
    heap.Init(q)
    fmt.Printf("
Adr: %p
", &q)
    q.Push(pq.NewItem("h", 2))

    for i := 0; i < 5; i++ {
        item := pq.NewItem("test", i * 13 % 7)
        heap.Push(q, item)
    }

    for q.Len() > 0 {
        fmt.Println("Item: " + heap.Pop(q).(string))
    }
}

As you can see when comparing to the example I do not use pointers since doing that will give me a compile error telling me that my priority queue does not implement the interface properly.

This leaves me with the following problem when I do:

heap.Push(q, item)

that the item is not appended to the queue.

I've tried to write out the queues pointer address and it shows different addresses. This explains why it does not work, but souldn't slices not be reference types a long with maps?

And more specificly: How do i solve my problem?

Hope you can help!

Edit: Added full code and error: cannot use q (type pq.PriorityQueue) as type heap.Interface in function argument: pq.PriorityQueue does not implement heap.Interface (Pop method has pointer receiver)

Answer 1

As the example code shows, the Push method must have a pointer receiver.

The trick is that all the calls to heap.XXX functions, require that you pass your heap in as a pointer (e.g.: heap.Init(&pq)). This is not the case in the code you posted. Here is a working version of your code. You can run it on the Go playground.

Note that in this code, I explicitly initialize the queue as a pointer: q := new(PriorityQueue). And this is what I pass in to all the heap functions.

The confusion here arises mostly because you are essentially implementing 2 interfaces. The heap.Interface and the sort.Interface (The latter is part of the prior's type definition). But the sort interface is fine with non-pointer receivers, while the other one is not.

package main

import "fmt"
import "container/heap"

func main() {
    q := new(PriorityQueue)

    heap.Init(q)

    fmt.Printf("
Adr: %p
", &q)
    q.Push(NewItem("h", 2))

    for i := 0; i < 5; i++ {
        heap.Push(q, NewItem("test", i*13%7))
    }

    for q.Len() > 0 {
        fmt.Println("Item: " + heap.Pop(q).(string))
    }
}

type Item struct {
    container interface{}
    priority  int
    index     int
}

type PriorityQueue []*Item

func NewItem(value interface{}, prio int) *Item {
    return &Item{container: value, priority: prio}
}

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
    fmt.Printf("adr: %p
", pq)
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    itm := old[n-1]
    itm.index = -1
    *pq = old[0 : n-1]
    return itm.container
}