Golang如何使用container/heap实现堆-Golang-PHP中文网

Golang如何使用container/heap实现堆

P粉602998670

发布： 2025-10-16 20:23:02

原创

270人浏览过

答案是container/heap包需实现heap.Interface接口，通过定义Len、Less、Swap、Push、Pop方法构建堆结构，如用IntHeap实现最小堆或最大堆，并可扩展至TaskHeap按优先级处理任务。

golang如何使用container/heap实现堆

在Go语言中，container/heap 是一个标准库包，提供了堆（优先队列）的接口和操作方法。它本身没有直接提供一个现成的堆结构，而是要求你实现一个满足 heap.Interface 接口的类型，然后通过 heap.Init、heap.Push、heap.Pop 等函数来操作这个堆。

1. 实现 heap.Interface 接口

要使用 container/heap，你需要定义一个类型（通常是切片），并实现以下五个方法：

Len() int：返回元素个数
Less(i, j int) bool：定义堆的排序规则（最小堆或最大堆）
Swap(i, j int)：交换两个元素
Push(x interface{})：向堆中添加元素
Pop() interface{}：从堆中移除并返回元素（通常是堆顶）

2. 创建一个最小堆示例

下面是一个整数最小堆的完整实现：

package main

import (
    "container/heap"
    "fmt"
)

// 定义一个整数切片类型
type IntHeap []int

// 实现 Len 方法
func (h IntHeap) Len() int           { return len(h) }

// Less 决定是小顶堆（<）还是大顶堆（>）
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // 最小堆

// Swap 交换元素
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push 添加元素（注意：接收者是指针）
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

// Pop 移除并返回堆顶元素
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{3, 1, 4, 1, 5}
    heap.Init(h)           // 初始化为堆
    heap.Push(h, 2)        // 插入元素
    fmt.Printf("最小值: %d\n", (*h)[0])
    
    for h.Len() > 0 {
        min := heap.Pop(h).(int)
        fmt.Print(min, " ")
    }
    // 输出: 1 1 2 3 4 5
}

登录后复制

3. 创建一个最大堆

只需修改 Less 方法的比较方向：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

立即学习“go语言免费学习笔记（深入）”；

func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // 最大堆

登录后复制

4. 处理复杂数据结构（如任务优先级）

实际开发中，堆常用于处理带优先级的对象。例如，按优先级调度任务：

type Task struct {
    ID       int
    Priority int
}

type TaskHeap []*Task

func (h TaskHeap) Len() int            { return len(h) }
func (h TaskHeap) Less(i, j int) bool  { return h[i].Priority < h[j].Priority } // 优先级小的先出（最小堆）
func (h TaskHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }

func (h *TaskHeap) Push(x interface{}) { *h = append(*h, x.(*Task)) }
func (h *TaskHeap) Pop() interface{} {
    old := *h
    n := len(old)
    task := old[n-1]
    *h = old[0 : n-1]
    return task
}

登录后复制