go - Go 的堆接口(interface)是如何工作的？

在 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

最佳答案

为了保持堆实现简单，您只需要为您的自定义类型提供排队逻辑。 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 - Go 的堆接口(interface)是如何工作的？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43132743/