深入了解Golang官方container/heap用法
作者:ag9920 发布时间:2024-05-13 10:44:42
开篇
在 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。
同时做一层简单的封装就可以对外使用了。
来源:https://juejin.cn/post/7152136155410989092
猜你喜欢
- 将源目录的图片用MD5命名并设定目标目录尝试了一下用 python 实现了一个生成密码的程序。感觉还是比较好上手的。但是那个程序还是非常简单
- 本文总结分析了MySQL查询优化的技巧。分享给大家供大家参考,具体如下:熟悉SQL语句的人都清楚,如果要对一个任务进行操作的话,SQL语句可
- 本文实例讲述了Python面向对象之类和实例用法。分享给大家供大家参考,具体如下:类虽然 Python 是解释性语言,但是它是面向对象的,能
- 没事在这里发一下关于数据库大批量插入数据的效率对比,用ACCESS和MSSQL,数值是在本机测试,根据不同的环境和配置,数值可能会有较大差别
- <div class=”A” style=”position:relative;”>A 
- 下面小编给大家介绍基于js如何从一组数据中找到指定的单条数据。具体方法如下所示:在一般情况下,我们会要求后端在列表的时候输出一堆列表的JSO
- 前言前段时间我有个朋友看到一些小姐姐的照片,想全部下载下来,叫我帮个忙。于是花费了半天给他全部下载了下来。引入库import timeimp
- 由于一些原因,需要SAE上站点的日志文件,从SAE上只能按天下载,下载下来手动处理比较蛋疼,尤其是数量很大的时候。还好SAE提供了API可以
- 方法一:<code class="language-python">""" 根
- django 创建过滤器一、需求来源:假如有一个模板文件有一个字符串变量,这个字符串变量中不能有任何的空格,而恰恰这个模板被很多个视图函数多
- 理科学生应该都了解过共轭吧,经常在数学或者物理还有化学中出现,在坐标轴上去描述共轭函数还是比较清晰的,py语言里也经常会出现关于共轭函数的使
- 第一题: give you two var a and b, print the value of a+b, just do it!根据提议
- 前言defer是golang语言中的关键字,用于资源的释放,会在函数返回之前进行调用。一般采用如下模式:f,err := os.Open(f
- 排序是个很泛的概念,而且根据被排序的数据量排序方法和侧重又有很大的不同。因此一直没想到从何着手。今天把玩iphone的时候突然又想到这个问题
- Python编程中raise可以实现报出错误的功能,而报错的条件可以由程序员自己去定制。在面向对象编程中,可以先预留一个方法接口不实现,在其
- PDF文件是一种常见的文档格式,但是在编辑和修改时不太方便,因为PDF本质上是一种静态的文档格式。因此,有时候我们需要将PDF文件转换成Wo
- 假如有个任务: 给定一个字符串,通过查询字典,来替换给定字符中的变量。如果使用通常的方法:>>> "This i
- pandas每次多Sheet写入文件,只能一次性存入,不然每次会重写文件,最后只保留最后一次的写入。# !usr/bin env pytho
- 例:公司员工采取三个轮班制度:凌晨0:00到早上8:00为第一班,早上8:00到下午4:00为第二班,下午4:00到晚上12:00为第三班。
- 在使用Tensor时,我们首先要掌握如何使用Tensor来定义不同数据类型的变量。Tensor时张量