Go语言实现最小堆（小白也能轻松掌握的数据结构）

为什么使用数组表示堆？

虽然堆是树形结构，但我们通常用数组来高效地存储它。因为堆是一棵完全二叉树，所以可以按层序遍历的方式将节点存入数组，这样父子节点之间有固定的索引关系：

• 对于索引为 i 的节点：
• 父节点索引： (i - 1) / 2
• 左子节点索引： 2*i + 1
• 右子节点索引： 2*i + 2

Go语言实现最小堆

下面我们用 Go 语言一步步实现一个最小堆。我们将封装成一个结构体，并提供插入、删除最小值、查看堆顶等方法。

1. 定义 MinHeap 结构体

type MinHeap struct {    data []int}

2. 初始化堆

func NewMinHeap() *MinHeap {    return &MinHeap{data: make([]int, 0)}}

3. 上浮操作（heapify up）

当新元素插入后，可能破坏堆的性质，需要将其“上浮”到合适位置。

func (h *MinHeap) heapifyUp(index int) {    for index > 0 {        parentIndex := (index - 1) / 2        if h.data[parentIndex] <= h.data[index] {            break        }        h.data[parentIndex], h.data[index] = h.data[index], h.data[parentIndex]        index = parentIndex    }}

4. 下沉操作（heapify down）

当堆顶被移除后，需将最后一个元素移到顶部并“下沉”以恢复堆性质。

func (h *MinHeap) heapifyDown(index int) {    lastIndex := len(h.data) - 1    for {        left := 2*index + 1        right := 2*index + 2        smallest := index        if left <= lastIndex && h.data[left] < h.data[smallest] {            smallest = left        }        if right <= lastIndex && h.data[right] < h.data[smallest] {            smallest = right        }        if smallest == index {            break        }        h.data[index], h.data[smallest] = h.data[smallest], h.data[index]        index = smallest    }}

5. 插入元素

func (h *MinHeap) Insert(val int) {    h.data = append(h.data, val)    h.heapifyUp(len(h.data) - 1)}

6. 删除最小值（堆顶）

func (h *MinHeap) ExtractMin() (int, bool) {    if len(h.data) == 0 {        return 0, false    }    min := h.data[0]    last := h.data[len(h.data)-1]    h.data = h.data[:len(h.data)-1]    if len(h.data) > 0 {        h.data[0] = last        h.heapifyDown(0)    }    return min, true}

7. 查看堆顶元素

func (h *MinHeap) Peek() (int, bool) {    if len(h.data) == 0 {        return 0, false    }    return h.data[0], true}

完整示例与测试

下面是一个完整的使用示例：

package mainimport "fmt"// （此处省略上述所有 MinHeap 方法定义）func main() {    heap := NewMinHeap()    heap.Insert(10)    heap.Insert(5)    heap.Insert(20)    heap.Insert(3)    fmt.Println("堆顶元素:", heap.Peek()) // 输出: 3    for {        if val, ok := heap.ExtractMin(); ok {            fmt.Print(val, " ") // 依次输出: 3 5 10 20        } else {            break        }    }}

应用场景

最小堆在实际开发中有广泛用途，例如：

• 实现优先队列（Priority Queue）
• 堆排序算法的核心
• Top-K 问题（如找出最小的 K 个数）
• 图算法中的 Dijkstra 最短路径

总结

通过本文，你已经学会了如何用 Go语言 实现一个功能完整的最小堆。这不仅加深了你对数据结构的理解，也为后续学习更复杂的算法（如堆排序）打下坚实基础。动手试试吧！

关键词：Go语言、最小堆、数据结构、堆排序