Go的堆接口如何工作？

Question

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

Answer 1

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()
}