英文:
How does Go's heap interface work?
问题
在Go语言中，你可以这样实现一个堆：https://golang.org/src/container/heap/example_pq_test.go
你需要实现sort.Interface、Pop和Push，这样你就得到了一个优先队列/堆。在Pop和Push的实现示例中，没有调用heap.Fix函数。我看到调用了heap.Init，所以我可以理解在这里进行了一些堆化操作。然而，你可以推入和弹出元素，运行自己的代码，而堆的属性仍然保持不变。
如果在初始化后推入或弹出元素而没有调用heap.fix，那么堆的属性是如何保持的呢？
这是一个示例的在线代码编辑器：https://play.golang.org/p/wE413xwmxE
英文:
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
答案1
得分: 4
为了保持堆实现的简单性，您只需要为自定义类型提供排队逻辑。堆化是由heap包自身完成的。它通过调用您类型上定义的Push/Pop方法，然后调用堆化过程来实现：
// 来自 golang.org/src/container/heap/heap.go
// Push 将元素 x 推入堆中。复杂度为 O(log(n))，其中 n = h.Len()。
//
func Push(h Interface, x interface{}) {
h.Push(x) // 调用自定义类型上定义的 Push 方法
up(h, h.Len()-1) // **堆化**
}
// Pop 从堆中移除最小的元素（根据 Less 方法），并返回它。复杂度为 O(log(n))，其中 n = h.Len()。
// 等价于 Remove(h, 0)。
//
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n) // **堆化**
return h.Pop()
}
以上是堆化过程的代码实现。
英文:
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()
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论