当前位置：首页 > 文章列表 > Golang > Go教程 > Golangheap包实现最小堆和最大堆示例

Golangheap包实现最小堆和最大堆示例

2025-12-17 23:35:29 0浏览收藏

推广推荐

支持 PC / 移动端，安全直达

在IT行业这个发展更新速度很快的行业，只有不停止的学习，才不会被行业所淘汰。如果你是Golang学习者，那么本文《如何在Golang中使用container/heap实现堆结构_最小堆和最大堆示例》就很适合你！本篇内容主要包括##content_title##，希望对大家的知识积累有所帮助，助力实战开发！

Go标准库container/heap不直接提供最小堆或最大堆类型，而是通过实现heap.Interface接口（含Len、Less、Swap及Push、Pop方法）配合heap函数使用；最小堆由Less返回a[i]a[j]；泛型封装可复用逻辑，支持任意类型和序关系；使用时需传指针、调用Init建堆、注意Pop行为。

如何在Golang中使用container/heap实现堆结构_最小堆和最大堆示例

Go 语言标准库 container/heap 并不直接提供最小堆或最大堆类型，而是提供一个通用的堆操作接口，需要你实现 heap.Interface（即 sort.Interface + 两个方法），再配合 heap.Init、heap.Push、heap.Pop 等函数使用。关键在于：最小堆和最大堆的区别，只取决于你如何定义 Less(i, j int) bool 方法。

最小堆：按元素值升序排列（小根堆）

要让堆顶始终是最小元素，只需在 Less 中返回 a[i] 。下面是一个基于整数切片的最小堆示例：

// 定义最小堆类型（包装 []int）

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] 
<p><font color="gray">// 使用示例</font></p>
<pre class="brush:php;toolbar:false;">h := &MinHeap{}
heap.Init(h)

heap.Push(h, 5)
heap.Push(h, 2)
heap.Push(h, 8)
heap.Push(h, 1)

fmt.Println(heap.Pop(h)) // 1
fmt.Println(heap.Pop(h)) // 2
fmt.Println(heap.Pop(h)) // 5

最大堆：按元素值降序排列（大根堆）

只需把 Less 的逻辑反过来：返回 a[i] > a[j]，其余代码完全一致：

// 定义最大堆类型

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // 关键：大的在前（即 i 更“小”当 h[i] 更大）
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

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

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

// 使用示例

h := &MaxHeap{}
heap.Init(h)

heap.Push(h, 5)
heap.Push(h, 2)
heap.Push(h, 8)
heap.Push(h, 1)

fmt.Println(heap.Pop(h)) // 8
fmt.Println(heap.Pop(h)) // 5
fmt.Println(heap.Pop(h)) // 2