Golang如何使用 container/heap 实现堆结构_Golang container/heap 优先队列示例-Golang-PHP中文网

Golang如何使用 container/heap 实现堆结构_Golang container/heap 优先队列示例

P粉602998670

发布： 2025-11-17 18:05:33

原创

270人浏览过

Go语言container/heap需实现heap.Interface接口，包括Len、Less、Swap、Push、Pop方法，通过heap.Init初始化堆，使用heap.Push和heap.Pop操作元素，适用于最小堆、优先队列等场景。

golang如何使用 container/heap 实现堆结构_golang container/heap 优先队列示例

Go 语言标准库 container/heap 提供了堆（优先队列）的接口和操作方法，但需要开发者自己实现底层数据结构并满足 heap.Interface 接口。它不是开箱即用的类型，而是基于接口的通用堆操作集合。

实现 heap.Interface 接口

要使用 container/heap，必须定义一个类型，并为其实现以下五个方法：

Len() int：返回元素个数
Less(i, j int) bool：定义堆序关系（如小顶堆或大顶堆）
Swap(i, j int)：交换两个元素位置
Push(x interface{})：向堆中添加元素
Pop() interface{}：从堆中移除并返回顶部元素

注意：Push 和 Pop 方法由 heap.Push 和 heap.Pop 调用，不会直接被用户调用，所以它们只负责把元素加入切片或从切片取出。

最小堆示例：整数小顶堆

下面是一个构建最小堆（小顶堆）的例子：

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

芦笋演示

一键出成片的录屏演示软件，专为制作产品演示、教学课程和使用教程而设计。

查看详情

package main

import (
    "container/heap"
    "fmt"
)

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

func (h IntHeap) Len() int           { return len(h) }
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] }

// Push 是 heap.Interface 的一部分，由 heap.Push 调用
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

// Pop 是 heap.Interface 的一部分，由 heap.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
}

登录后复制

优先队列示例：任务调度

实际应用中，堆常用于实现优先队列。比如按优先级处理任务：

package main

import (
    "container/heap"
    "fmt"
)

type Task struct {
    ID       int
    Priority int // 数值越小，优先级越高
}

type PriorityQueue []*Task

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Priority < pq[j].Priority // 小顶堆：优先级高的在前面
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    task := x.(*Task)
    *pq = append(*pq, task)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    task := old[n-1]
    *pq = old[0 : n-1]
    return task
}

func main() {
    pq := &PriorityQueue{}
    heap.Init(pq)

    heap.Push(pq, &Task{ID: 1, Priority: 3})
    heap.Push(pq, &Task{ID: 2, Priority: 1})
    heap.Push(pq, &Task{ID: 3, Priority: 2})

    fmt.Println("按优先级出队:")
    for pq.Len() > 0 {
        task := heap.Pop(pq).(*Task)
        fmt.Printf("任务 ID=%d, 优先级=%d\n", task.ID, task.Priority)
    }
}

登录后复制

输出结果会按照优先级顺序处理任务：

任务 ID=2, 优先级=1
任务 ID=3, 优先级=2
任务 ID=1, 优先级=3