Golangcontainer/heap实现堆数据结构示例-Golang-PHP中文网

Golangcontainer/heap实现堆数据结构示例

P粉602998670

发布： 2025-09-12 11:08:01

原创

503人浏览过

答案：Go语言通过container/heap包提供堆操作，需实现heap.Interface并使用heap.Init、heap.Push等函数初始化和维护堆结构。

golangcontainer/heap实现堆数据结构示例

Go语言标准库中的container/heap包提供了一个堆（优先队列）的接口实现，但不直接提供完整的堆类型。你需要先实现heap.Interface，然后使用heap.Init、heap.Push和

type IntHeap []int

// 实现 sort.Interface
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] }

// 实现 heap.Interface 的 Push 和 Pop
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

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

登录后复制

使用堆的基本操作

初始化堆，并进行插入、删除顶部元素等操作：

package main

import (
    "container/heap"
    "fmt"
)

func main() {
    h := &IntHeap{3, 1, 4, 1, 5}
    
    // 初始化堆
    heap.Init(h)
    
    // 插入元素
    heap.Push(h, 2)
    heap.Push(h, 6)
    
    // 弹出最小元素（最小堆）
    for h.Len() > 0 {
        min := heap.Pop(h).(int)
        fmt.Print(min, " ") // 输出: 1 1 2 3 4 5 6
    }
}

登录后复制

自定义结构体堆示例（如任务优先级）

更常见的场景是基于结构体字段排序，比如按优先级排序的任务：

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

PHP5 和 MySQL 圣经

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。

466

查看详情

type Task struct {
    ID       int
    Priority int
}

type TaskHeap []*Task

func (th TaskHeap) Len() int { return len(th) }

func (th TaskHeap) Less(i, j int) bool {
    return th[i].Priority < th[j].Priority // 优先级数值越小，越优先
}

func (th TaskHeap) Swap(i, j int) {
    th[i], th[j] = th[j], th[i]
}

func (th *TaskHeap) Push(x interface{}) {
    *th = append(*th, x.(*Task))
}

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

登录后复制

使用方式类似：

tasks := &TaskHeap{
    {ID: 1, Priority: 3},
    {ID: 2, Priority: 1},
    {ID: 3, Priority: 2},
}
heap.Init(tasks)
heap.Push(tasks, &Task{ID: 4, Priority: 0})

for tasks.Len() > 0 {
    task := heap.Pop(tasks).(*Task)
    fmt.Printf("Task ID: %d, Priority: %d\n", task.ID, task.Priority)
}
// 输出按优先级升序

登录后复制

基本上就这些。只要实现了heap.Interface（包含sort.Interface + Push/Pop），就能用container/heap管理你的数据结构。注意Push和Pop操作的是指针接收者，且必须配合heap包函数调用，不能直接调用。

以上就是Golangcontainer/heap实现堆数据结构示例的详细内容，更多请关注php中文网其它相关文章！