Go 的堆接口是如何工作的？

Question

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

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

如果您在 init 之后推送或弹出项目而不调用 heap.fix，堆 [=29=] 如何维护？

这是示例的 playground：https://play.golang.org/p/wE413xwmxE

Answer 1

为了简化堆实现，您只需为您的自定义类型提供排队逻辑。 Heapification 由 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()
}

Go 的堆接口是如何工作的？

How does Go's heap interface work?

heap

go