22
Go语言源码阅读(3) - container/heap | 堆
source link: https://www.tuicool.com/articles/aAFreeA
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
/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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK