Golang如何使用container/heap实现优先队列-Golang-PHP中文网

Golang如何使用container/heap实现优先队列

P粉602998670

发布： 2025-10-16 08:04:01

原创

355人浏览过

答案：Go语言通过container/heap包实现优先队列，需自定义类型并实现heap.Interface接口的五个方法；其中Len、Less、Swap为值接收者，Push和Pop为指针接收者；通过heap.Init初始化堆，heap.Push和heap.Pop进行入队出队操作；示例中以priority字段构建最小堆，优先级小的元素先出队；最终输出按优先级升序排列的结果。

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{}

其中 Less 方法决定了是最大堆还是最小堆。例如，若 Less(i, j) 表示 data[i] < data[j]，则是最小堆（小元素优先）。

2. 定义优先队列元素和队列结构

通常每个元素需要携带优先级值。下面是一个按优先级排序的最小堆优先队列示例：

Remove.bg

AI在线抠图软件，图片去除背景

174

查看详情

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

type Item struct {
    value    string
    priority int // 优先级越小，越优先
}

type PriorityQueue []*Item

// Len, Less, Swap
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]
}

// Push 往切片尾部添加元素
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Item)
    *pq = append(*pq, item)
}

// Pop 弹出最小优先级的元素
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

登录后复制

3. 使用优先队列

初始化堆后，就可以进行入队和出队操作：

package main

import (
    "container/heap"
    "fmt"
)

func main() {
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    // 插入元素
    heap.Push(&pq, &Item{value: "low", priority: 3})
    heap.Push(&pq, &Item{value: "high", priority: 1})
    heap.Push(&pq, &Item{value: "medium", priority: 2})

    // 按优先级弹出
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("value: %s, priority: %d\n", item.value, item.priority)
    }
}

登录后复制

输出结果为：

value: high, priority: 1
value: medium, priority: 2
value: low, priority: 3