深入了解Golang官方container/heap用法

目录
  • 开篇
  • container/heap
  • 核心函数
    • Init
    • Pop/Push
    • Remove
    • Fix
  • 如何接入
    • IntHeap
    • 优先队列
    • 按时间戳排序
  • 总结

开篇

在 Golang 的标准库 container 中,包含了几种常见的数据结构的实现,其实是非常好的学习材料,我们可以从中回顾一下经典的数据结构,看看 Golang 的官方团队是如何思考的。

  • container/list 双向链表;
  • container/ring 循环链表;
  • container/heap 堆。

今天我们就来看看 container/heap 的源码,了解一下官方的同学是怎么设计,我们作为开发者又该如何使用。

container/heap

包 heap 为所有实现了 heap.Interface 的类型提供堆操作。 一个堆即是一棵树, 这棵树的每个节点的值都比它的子节点的值要小, 而整棵树最小的值位于树根(root), 也即是索引 0 的位置上。

堆是实现优先队列的一种常见方法。 为了构建优先队列, 用户在实现堆接口时, 需要让 Less() 方法返回逆序的结果, 这样就可以在使用 Push 添加元素的同时, 通过 Pop 移除队列中优先级最高的元素了。

heap 是实现优先队列的常见方式。Golang 中的 heap 是最小堆,需要满足两个特点:

  • 堆中某个结点的值总是不小于其父结点的值;
  • 堆总是一棵完全二叉树。

所以,根节点就是 heap 中最小的值。

有一个很有意思的现象,大家知道,Golang 此前是没有泛型的,作为一个强类型的语言,要实现通用的写法一般会采用【代码生成】或者【反射】。

而作为官方包,Golang 希望提供给大家一种简单的接入方式,官方提供好算法的内核,大家接入就 ok。采用的是定义一个接口,开发者来实现的方式。

在 container/heap 包中,我们一上来就能找到这个 Interface 定义:

// The Interface type describes the requirements
// for a type using the routines in this package.
// Any type that implements it may be used as a
// min-heap with the following invariants (established after
// Init has been called or if the data is empty or sorted):
//
//	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
//
// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

除了 Push 和 Pop 两个堆自己的方法外,还内置了一个 sort.Interface:

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

核心函数

Init

作为开发者,我们基于自己的结构体,实现了 container/heap.Interface,该怎么用呢?

首先需要调用 heap.Init(h Interface) 方法,传入我们的实现:

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

在执行任何堆操作之前, 必须对堆进行初始化。 Init 操作对于堆不变性(invariants)具有幂等性, 无论堆不变性是否有效, 它都可以被调用。

Init 函数的复杂度为 O(n) , 其中 n 等于 h.Len() 。

Pop/Push

作为堆,当然需要实现【插入】和【弹出】这两个能力,这里 any 其实就是 interface{}

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}
  • Push 函数将值为 x 的元素推入到堆里面,该函数的复杂度为 O(log(n)) 。
  • Pop 函数根据 Less 的结果, 从堆中移除并返回具有最小值的元素, 等同于执行 Remove(h, 0),复杂度为 O(log(n))。(n 等于 h.Len() )

Remove

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

Remove 函数移除堆中索引为 i 的元素,复杂度为 O(log(n))

Fix

有时候我们改变了堆上的元素,需要重新排序。这时候就可以用 Fix 来完成。

这里需要注意:

  • 【先修改索引 i 上的元素的值然后再执行 Fix】
  • 【先调用 Remove(h, i) 然后再使用 Push 操作将新值重新添加到堆里面】

二者具有同等的效果。但 Fix 的成本会小一些。复杂度为 O(log(n))。

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

如何接入

将自定义结构实现上面的 heap.Interface 接口后,先进行 Init,随后调用上面我们提到的 Push / Pop / Remove / Fix 即可。其实大多数情况下用前两个就足够了,我们直接看两个例子。

IntHeap

先来看一个简单例子,基于整型 integer 实现一个最小堆。

  • 首先定义一个自己的类型,在这个例子中是 int,所以这一步跳过;
  • 定义一个 Heap 类型,这里我们使用 type IntHeap []int
  • 实现自定义 Heap 类型的 5 个方法,三个 sort 的,加上 Push 和 Pop。

有了实现,我们 Init 后就可以 Push 进去元素了,这里我们初始化 2,1,5,又 push 了个 3,最后打印结果完美按照从小到大输出。

// This example demonstrates an integer heap built using the heap interface.
package main

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
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] }

func (h *IntHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

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

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

Output:
minimum: 1
1 2 3 5

优先队列

官方也给出了实现优先队列的方法,我们需要一个 priority 作为权值,加上 value。

  • Value 表示元素值
  • Priority 用于排序
  • Index 元素在对上的索引值,用于更新元素的操作。
// This example demonstrates a priority queue built using the heap interface.
package main

import (
	"container/heap"
	"fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
	value    string // The value of the item; arbitrary.
	priority int    // The priority of the item in the queue.
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

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

func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

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

func (pq *PriorityQueue) Push(x any) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func main() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(&pq, item)
	pq.update(item, item.value, 5)

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
}

Output
05:orange 04:pear 03:banana 02:apple

按时间戳排序

package util

import (
	"container/heap"
)

type TimeSortedQueueItem struct {
	Time  int64
	Value interface{}
}

type TimeSortedQueue []*TimeSortedQueueItem

func (q TimeSortedQueue) Len() int           { return len(q) }
func (q TimeSortedQueue) Less(i, j int) bool { return q[i].Time < q[j].Time }
func (q TimeSortedQueue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }

func (q *TimeSortedQueue) Push(v interface{}) {
	*q = append(*q, v.(*TimeSortedQueueItem))
}

func (q *TimeSortedQueue) Pop() interface{} {
	n := len(*q)
	item := (*q)[n-1]
	*q = (*q)[0 : n-1]
	return item
}

func NewTimeSortedQueue(items ...*TimeSortedQueueItem) *TimeSortedQueue {
	q := make(TimeSortedQueue, len(items))
	for i, item := range items {
		q[i] = item
	}
	heap.Init(&q)
	return &q
}

func (q *TimeSortedQueue) PushItem(time int64, value interface{}) {
	heap.Push(q, &TimeSortedQueueItem{
		Time:  time,
		Value: value,
	})
}

func (q *TimeSortedQueue) PopItem() interface{} {
	if q.Len() == 0 {
		return nil
	}

	return heap.Pop(q).(*TimeSortedQueueItem).Value
}

这里我们封装了一个 TimeSortedQueue,里面包含一个时间戳,以及我们实际的值。实现之后,就可以暴露对外的 NewTimeSortedQueue 方法用来初始化,这里调用 heap.Init。

同时做一层简单的封装就可以对外使用了。

总结

Go语言中heap的实现采用了一种 “模板设计模式”,用户实现自定义堆时,只需要实现heap.Interface接口中的函数,然后应用heap.Push、heap.Pop等方法就能够实现想要的功能,堆管理方法是由Go实现好的,存放在heap中。

到此这篇关于深入了解Golang官方container/heap用法的文章就介绍到这了,更多相关Golang container/heap用法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 解决golang中container/list包中的坑

    golang中list包用法可以参看这篇文章 但是list包中大部分对于e *Element进行操作的元素都可能会导致程序崩溃,其根本原因是e是一个Element类型的指针,当然其也可能为nil,但是golang中list包中函数没有对其进行是否为nil的检查,变默认其非nil进行操作,所以这种情况下,便可能出现程序崩溃. 1.举个简单例子 Remove()函数 package main import ( "container/list" "fmt" ) func

  • 基于golang中container/list包的用法说明

    list是一个双向链表 该结构具有链表的所有功能. type Element type Element struct { Value interface{} //在元素中存储的值 } func (e *Element) Next() *Element //返回该元素的下一个元素,如果没有下一个元素则返回nil func (e *Element) Prev() *Element//返回该元素的前一个元素,如果没有前一个元素则返回nil. type List func New() *List //返

  • Go container包的介绍

    目录 1.简介 2.list 2.1数据结构 2.2插入元素 3.ring 3.1数据结构 4.heap 4.1数据结构 1.简介 Container - 容器数据类型:该包实现了三个复杂的数据结构:堆.链表.环 List:Go中对链表的实现,其中List:双向链表,Element:链表中的元素 Ring:实现的是一个循环链表,也就是我们俗称的环 Heap:Go中对堆的实现 2.list 简单实用: func main() { // 初始化双向链表 l := list.New() // 链表头插

  • 深入了解Golang官方container/heap用法

    目录 开篇 container/heap 核心函数 Init Pop/Push Remove Fix 如何接入 IntHeap 优先队列 按时间戳排序 总结 开篇 在 Golang 的标准库 container 中,包含了几种常见的数据结构的实现,其实是非常好的学习材料,我们可以从中回顾一下经典的数据结构,看看 Golang 的官方团队是如何思考的. container/list 双向链表: container/ring 循环链表: container/heap 堆. 今天我们就来看看 cont

  • GoLang中Json Tag用法实例总结

    目录 前言 Json中Tag用法汇总 官方 Marshal 函数说明 参考 总结 前言 GoLang中结构体的 JSON Tag 标识(英文名backquote或backtick,反引号 ` 符号包裹的部分内容)一直未明确看过完整规范和使用说明,存在模棱两可,系统整理如下: JSON Tag标签的完整语法,包含哪些选项 不同选项(输出名/-/omitempty/string)的作用及使用范围 特殊注意事项补充 Json中Tag用法汇总 JSON Tag标签格式为:json:"FieldName/

  • Go官方限流器的用法详解

    目录 限流器的内部结构 构造限流器 使用限流器 Wait/WaitN Allow/AllowN Reserve/ReserveN 动态调整速率和桶大小 总结 限流器是提升服务稳定性的非常重要的组件,可以用来限制请求速率,保护服务,以免服务过载.限流器的实现方法有很多种,常见的限流算法有固定窗口.滑动窗口.漏桶.令牌桶 简单来说,令牌桶就是想象有一个固定大小的桶,系统会以恒定速率向桶中放 Token,桶满则暂时不放.在请求比较的少的时候桶可以先"攒"一些Token,应对突发的流量,如果桶

  • Golang 官方依赖注入工具wire示例详解

    目录 依赖注入是什么 开源选型 wire providers injectors 类型区分 总结 依赖注入是什么 Dependency Injection is the idea that your components (usually structs in go) should receive their dependencies when being created. 在 Golang 中,构造一个结构体常见的有两种方式: 在结构体初始化过程中,构建它的依赖: 将依赖作为构造器入参,传入进

  • golang简单tls协议用法完整示例

    本文实例讲述了golang简单tls协议用法.分享给大家供大家参考,具体如下: 生成私钥: openssl genrsa -out key.pem 2048 生成证书: openssl req -new -x509 -key key.pem -out cert.pem -days 3650 https: 复制代码 代码如下: package main import (     "io"     "net/http"     "log" ) fun

  • 详解Golang中Channel的用法

    如果说goroutine是Go语言程序的并发体的话,那么channels则是它们之间的通信机制.一个channel是一个通信机制,它可以让一个goroutine通过它给另一个goroutine发送值信息. 1 创建channel 每个channel都有一个特殊的类型,也就是channels可发送数据的类型.一个可以发送int类型数据 的channel一般写为chan int.使用内置的make函数,如果第二个参数大于0,则表示创建一个带缓存的channel. ch := make(chan in

  • golang官方嵌入文件到可执行程序的示例详解

    前言 在go官方出嵌入文件的方法前我在网上找过,并且自己还研究过,虽然没有问题,但是既然官方支持还是用起来吧. 看了下go源码embed/embed.go很简单,并且看embed/internal/embedtest/embed_test.go就知道如何使用. 示例程序 嵌入文件直接访问 原理是使用go:embed标签来完成.下面是直接读取文件内容,需要注意下面几点. 文件不是utf8编码时,输出内容为中文会乱码. 测试过嵌入文件只能为源码文件同级目录和子目录下的文件,试过其他目录的绝对路径或相

  • Go官方工具链用法详解

    Go官方工具链 为了从任意目录运行Go官方工具链中工具命令(通过go命令), Go官方工具链安装目录下的bin子目录路径必须配置在PATH环境变量中. 当使用安装程序安装Go官方工具链时,安装程序很可能已经自动地将此配置好了.windows环境中需要在把安装目录下bin子目录添加到高级系统环境变量中保存生效. Go官方工具链近来的版本都支持一个称为Go模块(Go modules)的特性, 用来管理项目依赖.此特性在版本1.11中被试验性引入, 在版本1.16中被默认支持. 第一个环境变量 我们应

  • Golang官方限流器库实现限流示例详解

    目录 前言 例子 实现 小结 前言 在翻Golang官方库的过程中,发现一个有趣的库golang.org/x/time ,里面只有一个类rate,研究了一下发现它是一个限流器,实现了很多的功能,当然它的核心原理并不复杂,也就是令牌桶算法. 令牌桶算法的原理是:令牌桶会不断地把令牌添加到桶里,而请求会从桶中获取令牌,只有拥有令牌地请求才能被接受.因为桶中可以提前保留一些令牌,所以它允许一定地突发流量通过. 例子 下面是限流算法常见的写法,首先判断是否有令牌,如果有就通过,否则直接失败. packa

随机推荐