How do you use the heap package in Go?

Question

I've been trying to use the Heap package in Go and I am not sure on how to initialize it.

package main
import "container/heap"

type PriorityMessage struct {
    Priority int
    Message string
}

func priorityQueue() {
    //WOULD THIS not initialize the heap?
    h := heap.Init(h PriorityMessage)

}

I've been trying to find examples online of how other's initialized their heaps and all of them seem to create their own versions of the Go heap package everytime. Would calling the heap.Init(h Interface) function from the heap package not work?

Koontz

See the example in the documentation. – Plangent

That's what I was confused about, just like how in this example how they create the push, pop, len .etc functions, every time you wanted to use a heap would you have to write those functions as well or could you just call it from the heap package? – Koontz

See the Interface documentation. The application provides simple operations for accessing the underlying data. The heap package uses those operations to implement heap semantics. – Plangent

@Koontz Yes, of course. – Ruthful

You can see the usage of container/heap package in this post along with some example usage: tugberkugurlu.com/archive/… – Roehm

Answer 1

There is the heap.Interface what you should implement first.

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

This means you should have the necessary methods for your PriorityMessage struct. After you pass the instance of the struct into the heap.Init(&pm).

You can find details in the godoc as linked in the comments.

Just to clarify the confusion. Go is a strongly typed language with lack of generics. So the heap package designed on the way that it's type independent. You can create your own implementation for all of the types what you want to implement. Any type implements the heap.Interface can be used by the heap package.

Equable

"Go is a strongly typed language with lack of generics" this isn't true anymore. I'm surprised that pkg.go.dev/container/heap wasn't updated to support it. – Olympus

Answer 2

  //https://cs.opensource.google/go/go/+/refs/tags/go1.16.6:src/container/heap/example_intheap_test.go 
    
    // This example demonstrates an integer heap built using the heap interface.
    //package heap_test
    
    import (
        "container/heap"
        "fmt"
    )
    
    // An IntHeap is a min-heap of ints.
    type IntHeap []int
    
    func (h IntHeap) Len() int           { return len(h) }
    func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
    func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    
    func (h *IntHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *h = append(*h, x.(int))
    }
    
    func (h *IntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
    }
    
    // This example inserts several ints into an IntHeap, checks the minimum,
    // and removes them in order of priority.
    func Example_intHeap() {
        h := &IntHeap{2, 1, 5}
        heap.Init(h)
        heap.Push(h, 3)
        fmt.Printf("minimum: %d\n", (*h)[0])
        for h.Len() > 0 {
            fmt.Printf("%d ", heap.Pop(h))
        }
        // Output:
        // minimum: 1
        // 1 2 3 5
    }

Clarethaclaretta

Little bit explanation would be nicer. – Anathematize

added a tutorial here youtube.com/watch?v=qDP1FCT6qZ4 – Cloudlet

Answer 3

The heap package expects that you provide an object that meets the heap.Interface. So, in the example, both IntHeap and PriorityQueue are the objects that meet the interface. I think that the confusion is that most people would expect the example to work differently e.g.

    q := NewMinimumPriorityQueue()
    q.Push("A", 1)
    q.Push("E", 5)
    q.Push("D", 4)
    q.Push("B", 2)
    item := q.Pop() // giving A

To be able to achieve this, it needs 2 objects implemented:

• A store (heap) that meets heap.Interface
• A priority queue

So the heap implementation for a min priority queue would be something like:

type element struct {
    priority int
    data     any
    index    int
}

type store []*element

func (s *store) Len() int {
    return len(*s)
}

func (s *store) Less(i, j int) bool {
    h := *s
    return h[i].priority < h[j].priority
}

func (s *store) Swap(i, j int) {
    h := *s
    h[j], h[i] = h[i], h[j]
    h[i].index = i
    h[j].index = j
}

func (s *store) Push(x any) {
    h := *s
    h = append(h, x.(*element))
    *s = h
}

func (s *store) Pop() any {
    h := *s
    n := len(h)
    if len(h) > 0 {
        el := h[n-1]
        *s = h[0 : n-1]
        return el
    }
    return nil
}

The public min priority queue implementation:

type MinimumPriorityQueue struct {
    store store
}

func NewMinimumPriorityQueue() *MinimumPriorityQueue {
    q := &MinimumPriorityQueue{
        store: make([]*element, 0),
    }
    heap.Init(&q.store)
    return q
}

func (q *MinimumPriorityQueue) Push(data any, priority int) {
    // append the element to the store
    el := &element{
        priority: priority,
        data:     data,
        index:    q.store.Len(),
    }
    heap.Push(&q.store, el)

    // fix the store order
    heap.Fix(&q.store, el.index)
}

func (q *MinimumPriorityQueue) Pop() any {
    if q.Len() == 0 {
        return nil
    }

    el := heap.Pop(&q.store)
    if el == nil {
        return nil
    }

    return el.(*element).data
}

Store the store is an internal, low-level implementation that is used by the public MinimumPriorityQueue.

Evadne