Go 实现堆

在 Go 语言中，可以使用标准库 container/heap 来实现最小堆，它提供了一个 heap.Interface 接口，需要实现三个方法：

Len() int：返回堆的元素个数
Less(i, j int) bool：返回第 i 个元素是否比第 j 个元素小
Swap(i, j int)：交换第 i 个元素和第 j 个元素

然后，可以使用 container/heap 提供的堆操作函数：

heap.Push(heap Interface, x interface{})：将元素 x 插入堆中
heap.Pop(heap Interface) interface{}：从堆中取出并删除堆顶元素
heap.Init(heap Interface)：将切片转换为堆
heap.Remove(heap Interface, i int) interface{}：删除第 i 个元素

下面是一个使用 container/heap 实现最小堆的示例代码：

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int

func (h MinHeap) Len() int {
    return len(h)
}

func (h MinHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &MinHeap{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}
    heap.Init(h)

    fmt.Printf("堆中最小值: %d\n", (*h)[0])

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

输出

1 2	堆中最小值: 1 1 1 2 3 3 4 5 5 5 6 9

在 Go 语言中，实现小顶堆需要实现 heap.Interface 接口，该接口定义了三个方法：

Len() int
Less(i, j int) bool
Swap(i, j int)

其中，Len() 方法返回堆中元素的数量，Less() 方法用于定义元素的比较规则，Swap() 方法用于交换堆中的两个元素的位置。

在实现小顶堆时，需要定义 Less() 方法，用于指定元素的比较规则。具体来说，Less() 方法应该返回 true，当且仅当第一个参数小于第二个参数时。这个比较规则可以根据实际需要来定义，例如可以按照元素大小进行比较，也可以按照元素的时间戳等其他属性进行比较。

同时，Swap() 方法也是必须实现的。它用于交换堆中两个元素的位置，以确保堆的正确性。具体来说，Swap() 方法接收两个索引作为参数，然后将这两个索引所对应的元素交换位置。

在实现小顶堆时，Len() 方法可以直接使用 Go 内置的 len() 函数，因为堆中元素的数量就是 slice 的长度。因此，我们只需要实现 Less() 和 Swap() 两个方法即可。

Go 实现 堆

Go 实现堆