Go语言源码阅读(3) - container/heap | 堆

/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

原文链接: https://pengrl.com/p/40957/
原文出处: yoko blog (https://pengrl.com)
原文作者: yoko
版权声明: 本文欢迎任何形式转载,转载时完整保留本声明信息(包含原文链接、原文出处、原文作者、版权声明)即可。本文后续所有修改都会第一时间在原始地址更新。

0%