/src/container/heap
除了支持建堆(Init)、插入(Push)、删除堆顶元素(Pop)的常规操作外,还支持删除指定位置元素(Remove)、指定位置元素的值发生变化后堆重新 排序 的操作(Fix)。
实现手法是提供了一系列自身无状态的函数(后续称这些函数为 系统库函数
),系统库函数内部实现堆的算法,并在需要操作容器的时候(也就是在算法中的合适位置)调用用户实现了 heap.Interface
接口的结构体对象(或者叫容器)的方法。
算法部分采用二叉堆。
由于系统库函数并不直接访问用户层的数据(只能通过用户类型实现 heap.Interface
的方法来操作用户的数据),从某种角度来说,用户甚至可以使用链表而非数组作为容器。当然,那样的话用户层所有通过下标访问数据的操作就变复杂了,复杂度也增加了。不会真有人这么做。这里只为说明 Go 这种抽象手法的灵活性。
/src/container/heap/example_intheap_test.go
中演示了如何实现一个存放基础类型int数组切片的最小堆。
如果是最大堆,只需将接口 Less
中的实现修改为大于即可。
/src/container/heap/example_pq_test.go
中演示了如何实现自定义结构体类型堆,另一方面实现了优先级队列( PriorityQueue
),它比上面 intheap
例子中多了一个操作,可对堆中元素做修改,然后让堆重新调整保证堆特性。
基于 Go 1.11.4
以上所述就是小编给大家介绍的《Go语言源码阅读(3) - container/heap | 堆》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 如何为 Go 语言源码仓库贡献代码
- Go 语言中的锁源码实现:Mutex
- Go语言源码阅读(4) - container/list | 链表
- Go语言源码阅读(5) - container/ring | 环形链表
- 木兰语言 0.0.17:着手由 Python 语法树生成木兰源码
- 木兰语言 0.0.17.1:源码生成支持更多函数、类相关语法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Head First JavaScript程序设计
[美]Eric T. Freeman、[美] Elisabeth Robson / 袁国忠 / 人民邮电出版社 / 2017-9 / 129.00 元
本书语言和版式活泼,内容讲解深入浅出,是难得的JavaScript入门书。本书内容涵盖JavaScript的基本知识以及对象、函数和浏览器文档对象模型等高阶主题。书中配备了大量有趣的实例、图示和练习,让读者轻轻松松掌握JavaScript。一起来看看 《Head First JavaScript程序设计》 这本书的介绍吧!