Go 的堆接口如何工作？

Question

在 Go 中，您可以这样实现堆：https://golang.org/src/container/heap/example_pq_test.go

您实现了sort.Interface、Pop、 和Push，并且您已经拥有了一个优先级队列/堆。Pop在和Push实现的示例中，heap.Fix未调用该函数。我看到它heap.Init被调用了，所以我可以理解当时发生的一些堆化。但是，您可以推送和弹出项目，这会运行您自己的代码，并且会维护堆属性。

如果您在 init 之后推送或弹出项目而不调用heap.fix，那么如何维护堆属性？

这是示例的游乐场：https ://play.golang.org/p/wE413xwmxE

Answer 1

为了保持堆实现简单，您只需为自定义类型提供排队逻辑。堆化是由heap包本身完成的。它通过调用在您的类型上定义的Push/来实现这一点Pop，然后调用堆化过程：

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