In Go, you can implement a heap as such: https://golang.org/src/container/heap/example_pq_test.go
You implement the sort.Interface
, Pop
, and Push
and you've got yourself a priority queue/heap. In the example of both Pop
and Push
implementations the heap.Fix
function isn't called. I see that heap.Init
is called, so I can understand some heap-ifying happening then. However, you are able to push and pop items, which runs your own code, and the heap property is maintained.
If you push or pop items after init without calling heap.fix
, how does the heap property get maintained?
Here's a playground of the example: https://play.golang.org/p/wE413xwmxE
To keep heap implementation simple, you are only required to provide queuing logic for your custom type. Heapification is done by the heap
package itself. It does so by calling the Push
/Pop
defined on your type, and then calling the heapification procedure:
// from golang.org/src/container/heap/heap.go
// Push pushes the element x onto the heap. The complexity is
// O(log(n)) where n = h.Len().
//
func Push(h Interface, x interface{}) {
h.Push(x) // call to Push defined on your custom type
up(h, h.Len()-1) // **heapification**
}
// Pop removes the minimum element (according to Less) from the heap
// and returns it. The complexity is O(log(n)) where n = h.Len().
// It is equivalent to Remove(h, 0).
//
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n) // **heapification**
return h.Pop()
}