first of all, the HEAP

就不介绍堆的基础知识啦

为了了解这个包，我们首先从堆这个概念入手。我刷面经的时候，也算是把堆的各种题目都已经做了遍，所以对于堆排序的算法也算是比较熟悉了，那么就从这里入手吧。

先手撕一个大顶堆实现的堆排序算法：

  1. // 堆排序
  2. func heapSort(arr []int) {
  3.   buildMaxHeap(arr, len(arr))
  4.   for i := len(arr) - 1; i > 0; i-- {
  5.       arr[i], arr[0] = arr[0], arr[i]
  6.     maxHeapify(arr, 0, i)
  7.   }
  8. }
  10. // 建堆
  11. func buildMaxHeap(arr []int, length int) {
  12.   for i := length >> 1; i >= 0; i-- {
  13.     maxHeapify(arr, i, length)
  14.   }
  15. }
  17. // 调整大顶堆的某一个节点
  18. func maxHeapify(arr []int, index, length int) {
  19.   l := left(index)
  20.   r := right(index)
  21.   max := index
  23.   if l < length && arr[l] > arr[max] {
  24.       max = l
  25.   } 
  26.   if r < length && arr[r] > arr[max] {
  27.       max = r
  28.   }
  29.   if max != index {
  30.       arr[max], arr[index] = arr[index], arr[max]
  31.     maxHeapify(arr, max, length)
  32.   }
  33. }
  35. // 定位左子节点
  36. func left(i int) int {
  37.     return 1 + i << 1
  38. }
  40. // 定位右子节点
  41. func right(i int) int {
  42.     return 2 + i << 1
  43. }

虽然和官方包提供的使用方式不同，但是也可留以与官方包中的内容进行对比

container.heap

1 包介绍

go的官方包的目标当然更加长远，是要为我们提供一个易于使用的容器。我们参考pkg.go.dev中对这个包的描述，就可以看到关于包的描述：

  • 包heap为任何实现了heap.Interface的类型提供堆操作。堆是一棵树，其特性是每个节点都是其子树中价值最小的节点。也就是说，（默认的规则是小顶堆）
  • 树中的最小元素是根，索引为0
  • 堆是实现优先级队列的一种常见方式。想要建立一个优先级队列，就实现heap.Interface接口，将（负）优先级作为Less方法的排序，因此Push增加项目，而Pop从队列中删除最高优先级的项目。实例中包括这样一个实现：文件example_pq_test.go中有完整的源代码

非常明显，这个包的核心就是提供了heap.Interface接口，通过实现这个接口需要的排序、添加项目与删除项目的相关逻辑，就实现了一个小顶堆。

而在heap包中，还实现了Init、Push、Pop、Remove、Fix、up、down等方法，来提供调用的接口以及内部的实现

2 heap.Interface

非常简单：

  1. // Interface类型描述了使用本包例程的需求
  2. // 任何实现了Interface接口的类型都可以当做最小堆使用，
  3. // （在调用Init后或数据为空或被排序后建立）并具有以下的不变性：
  4. // 
  5. // !h.Less(j, i) for 0 <= i < h.Len() and
  6. // 2*i+1 <= j <= 2*i+2 and j < h.Len()
  7. type Interface interface {
  8.     sort.Interface
  9.     Push(x interface{}) // add x as element Len()
  10.     Pop() interface{}   // remove and return element Len() - 1.
  11. }

首先看看注释，有了自己手撕堆的经验就很容易看出，这个不变形表达的是：如果j是i的子节点，则Less(j, i)一定不成立。也就是说一定会维持小顶堆的结构。

Push和Pop的含义自然就是添加和删除元素，我们最要关注的是sort.Interface这个接口，定义了哪些内容：

  1. // Interface的实现可以通过这个包中的例程进行排序。
  2. // 这些方法通过整数索引来引用底层集合的元素
  3. type Interface interface {
  4.     // 元素的个数
  5.     Len() int
  7.     // Less 用于报告第i个元素是否排在第j个元素之前
  8.     //
  9.     // 如果Less(i,j)和Less(j,i)的返回值都是FALSE，则认为元素i与元素j相等
  10.     // 
  11.     // Sort方法可能是不稳定的，而Stable方法是稳定的排序
  12.     // 
  13.     // Less 必须描述一个可传递性的排序:
  14.     //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
  15.     //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
  16.     //
  17.     // 注意，浮点比较（float32或float64值的<操作符），当涉及到
  18.     // 非数字（NaN）值时，不是一个传递性排序。
  19.     // See Float64Slice.Less for a correct implementation for floating-point values.
  20.     Less(i, j int) bool
  22.     // Swap swaps the elements with indexes i and j.
  23.     Swap(i, j int)
  24. }

这个文档已经非常详细了，没有什么需要多补充的，看看就知道啦

3 接口函数

Init

  • Init函数建立了本包中其他例程所需要的堆不变形
  • 对于堆不变性来说，Init是等价的，只要堆不变性可能失效了，就可以调用它
  • 复杂度为O(n)，其中n = h.Len()
    1. func Init(h Interface) {
    2.   // heapify
    3.   n := h.Len()
    4.   for i := n/2 - 1; i >= 0; i-- {
    5.       down(h, i, n)
    6.   }
    7. }
    如果还记得我们的buildMaxHeapify函数，你就会发现，这俩就是一个意思，那么down函数大概率就是我们的maxHeapify啦

    Push

  1. func Push(h Interface, x interface{}) {
  2.     h.Push(x)
  3.     up(h, h.Len()-1)
  4. }

Pop

Remove

Fix