在算法题目中，我们经常遇到需要动态维护一个集合的最值（最大或最小值）的场景，例如找出动态数据流中的第 K 大元素、Dijkstra 算法中的节点松弛操作等。这些场景的共同特点是，我们不仅需要找到当前的最值，还需要高效地添加新元素和删除最值。 优先队列 (Priority Queue) 是实现这种操作的理想抽象数据结构，而 堆 (heap) 则是实现优先队列最常用、最高效的具体数据结构。
Golang 的标准库 container/heap 提供了一套堆操作的算法。需要注意的是，它并没有提供一个可以直接使用的、开箱即用的堆类型，而是定义了一个需要用户自己实现的接口 heap.Interface 。用户需要提供一个满足该接口的数据类型（通常是一个切片），container/heap 包中的函数，如 heap.Push 和 heap.Pop ，会基于用户提供的类型来维护堆的性质。
这种设计体现了 Go 语言接口的哲学：定义行为，而不是具体实现。它给予了开发者极大的灵活性，让我们可以对任意类型的集合实现堆操作，无论是整数、字符串还是自定义的结构体。
堆的内存布局
从逻辑上讲，堆是一个 完全二叉树 (Complete Binary Tree) 。这意味着除了最底层外，其他层都是完全填满的，并且最底层的节点都尽可能地靠左排列。然而，在物理存储上，堆并不会像链表那样使用指针来连接父子节点。相反，它被巧妙地存储在一个连续的内存空间中，比如 Golang 中的 切片 (slice) 或数组。
这种设计带来了巨大的性能优势：它不需要额外的指针开销，并且由于数据是连续存储的，可以更好地利用 CPU 缓存，提高访问效率。
我们通过切片的索引 i 就可以计算出任意节点的父节点和子节点的索引：
- 假设一个节点的索引为 i（i 从 0 开始）：
- 它的左子节点的索引是 2*i + 1
- 它的右子节点的索引是 2*i + 2
- 它的父节点的索引是 (i - 1) / 2 （整数除法，自动向下取整）
heap.Interface 与官方示例
Go 提供了 container/heap 这个包来实现堆的操作。堆实际上是一个树的结构，每个元素的值都是它的子树中最小的，因此根节点 index = 0 的值是最小的，即最小堆。
堆也是实现优先队列 Priority Queue 的常用方式。
堆中元素的类型需要实现 heap.Interface 这个接口：
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
其中 sort.Interface 包括 Len(), Less, Swap 方法：这意味着任何想要实现堆操作的类型，都必须首先实现 sort.Interface，即以下三个方法：
- Len() int: 返回集合中元素的数量。
- Less(i, j int) bool: 比较索引 i 和 j 处的元素。如果 h[i] 应该排在 h[j] 前面，则返回 true。对于 最小堆 ，这意味着 h[i] < h[j]；对于 最大堆 ，则是 h[i] > h[j]。
- Swap(i, j int): 交换索引 i 和 j 处的元素。
除此之外，还需要实现两个特定于堆的方法：
- Push(x any): 在集合的“末尾”添加一个新元素 x。通常，这意味着将元素 append 到切片的末尾。
- Pop() any: 从集合的“末尾”移除并返回一个元素。通常，这意味着移除并返回切片的最后一个元素。
一个完整的示例如下：
注意注释中的一句话 Push 和 Pop 方法需要使用指针，因为它们会修改 slice 的长度，而不仅仅只内容
import (
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
// Less 决定是大顶堆还是小顶堆，此处实现的是小顶堆
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0]) // minimum: 1
for h.Len() > 0 {
// 如果堆中的元素个数大于k，则把最后一个节点踢出堆
//（由于大顶堆的排序，最后一个节点肯定是所有节点中最大的节点）
fmt.Printf("%d ", heap.Pop(h)) // 1 2 3 5
}
}
疑问 ：为什么 Pop 方法是移除 最后一个 元素，而不是堆顶元素（索引为 0 的元素）？这正是 container/heap 包算法设计的巧妙之处。当我们调用 heap.Pop(h) 时，该函数会：
- 首先将堆顶元素（h[0]）与堆的最后一个元素（h[len(h)-1]）交换位置。此时，原本的最值（最小或最大元素）已经被移动到了切片的末尾。
- 然后，heap.Pop 会调用我们自己实现的 Pop() 方法。我们的 Pop() 方法只需要简单地移除并返回切片的最后一个元素即可，这个元素正是我们所需要的原堆顶元素。
- 最后，heap.Pop 内部会调整堆，使得除最后一个元素外，剩下的 n-1 个元素重新满足堆的性质。
container/heap 核心 API
现在我们来详细解释一下 heap 包提供的几个核心函数：
- func Init(h Interface) 此函数用于将一个无序的、满足 Interface 的数据集合整理成一个合法的堆。它的实现方式是从最后一个非叶子节点开始，自下而上、自右向左地对每个子树调用 down（一个内部函数）进行调整，使其满足堆的性质。时间复杂度为 O(n)，比逐个 Push 元素（O(n log n)）更高效。
- func Push(h Interface, x any) 向堆 h 中添加一个新元素 x。它首先调用用户定义的 Push(x) 方法将元素添加到数据集合的末尾，然后调用 up（一个内部函数）将这个新元素“上浮”到它在堆中的正确位置。时间复杂度为 O(log n)。
- func Pop(h Interface) any 从堆 h 中移除并返回堆顶元素（最小值或最大值）。如前所述，它通过将堆顶元素与最后一个元素交换，然后调用用户定义的 Pop() 方法来实现。之后，它会调用 down 将新的堆顶元素“下沉”到正确位置，以维持堆的性质。时间复杂度为 O(log n)。
- func Remove(h Interface, i int) any 移除并返回堆中索引为 i 的元素。这是一个更通用的删除操作。它的实现方式是将索引 i 的元素与最后一个元素交换，然后移除最后一个元素（即我们想删除的元素），最后对交换到位置 i 的新元素进行调整（可能上浮也可能下沉）来恢复堆的性质。时间复杂度为 O(log n)。
- func Fix(h Interface, i int) 当用户直接修改了堆中索引为 i 的元素的值（比如 PriorityQueue 例子中的 update 操作），这个元素的位置可能就不再满足堆的性质了。此时应调用 Fix(h, i)，该函数会自动地将该元素上浮或下沉到它新的正确位置，从而恢复整个堆的性质。i 就是被修改元素在底层切片中的索引。