Home

Using Package Heap

Saturday 24 November 2012

The documentation for the heap package includes an excellent example of a priority queue. But here's another anyway. The Go standard library is written so that you define the methods on the container, not on the elements as you would in C++ or Java. You must tell the compiler a few details about how your container works, and let it do the rest.
The interface of a heap is defined as
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}
so it builds on top of the sort.Interface, which is defined as
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less returns whether the element with index i should sort
    // before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}
This is known as "embedding an interface" and means that any type implementing interface A, where A embeds B, must implement the method set of B and the other methods of A. "To embed" means "to wrap", not "to be wrapped by".
type A interface{
    B //A embeds B
    methodA()
}
type B interface{
    methodB()
}
var a A
//can now call a.methodA() and a.methodB()
To take advantage of this I create a type that already implements sort.Interface and define methods on that type that make it implement heap.Interface, namely Push() and Pop(). I do this by using an anonymous or embedded field, which defines Len(), Swap(), Less() for IntHeap.
type IntHeap struct {
	sort.IntSlice
}
We cannot just write type IntHeap sort.IntSlice, as the method set of an underlying type does not transfer to other types.
Pop() removes and returns the minimum element from the heap and will panic if called on an empty heap. You can check if a heap is empty with the Len() method from the sort.Interface. Because Pop() modifies the length of the heap it needs to be defined on a pointer to a heap. It returns an interface{} because this container can be used to store any type. Since all types implement the empty interface, no type assertion is needed when we return an int.
func (h *IntHeap) Pop() interface{} {
	l := len(h.IntSlice)
	a := h.IntSlice[l-1]
	h.IntSlice = h.IntSlice[:l-1]
	return a
}
Push() adds an element to the end of the heap. Because we can pass anything to Push() we must use a type assertion before we append it to our slice of int. The append built-in will reallocate the slice if there is not enough memory for it to expand.
func (h *IntHeap) Push(x interface{}) {
	h.IntSlice = append(h.IntSlice, x.(int))
}
When using a heap you must use the functions defined in package heap, not the methods of the type you created. These functions will call the methods and those of sort.Interface to ensure the heap property is maintained. Fiddling around directly with the elements of the heap may mess things up, and you can call heap.Init() to restore order.

Previous (Binary Search)
Next (Error handling in Go)