Golang Heap 源码剖析

堆原理解析

堆一般指二叉堆。是使用完全二叉树这种数据结构构建的一种实际应用。通过它的特性，分为最大堆和最小堆两种。

如上图可知，最小堆就是在这颗二叉树中，任何一个节点的值比其所在子树的任意一个节点都要小。最大堆就是在这颗二叉树中，任何一个节点的值都比起所在子树的任意一个节点值都要大。

那么如何构建一个堆呢？首先要将所有的元素构建为一个完全二叉树。完全二叉树是指除叶子节点，所有层级是满节点，叶子节点从左向右排列填满。

在一个完全二叉树中，将数据重新按照堆的的特性排列，就可以将完全二叉树变成一个堆。这个过程叫做“堆化”。

在堆中，我们要删除一个元素一般从堆顶删除（可以取到最大值/最小值）。删除之后，数据集就不能算作一个堆了，因为最顶层的元素没有了，数据集不符合完全二叉树的定义。这时，我们需要将堆的数据进行重新排列，也就是重新“堆化”。同样的，在堆中新添加一个元素也需要重新做“堆化”的操作，来将数据集恢复到满足堆定义的状态。

所以，在堆这种数据结构中，最重要的是“堆化”的这个算法操作。其次，堆化数据如何存储也是很重要的。接下来，详细说一下。

完全二叉树的存储方式

对于二叉树来说，存储方式有2种，一种使用数组的形式来存储，一种使用链表的方式存储。同样的，这两种方式继承了这两种数据结构的坏处和好处。链表的方式相对浪费存储空间，因为要存储左右子树的指针，但扩缩容方便。而数组更加节省空间，更加方便定位节点，缺点则是扩缩容不便。

我们以数组的方式来做示例，了解存储的细节：

我们不用 \(index = 0\) 的位置来存储数据，而是从 \(index = 1\) 开始，这样，对于任意一个节点 \(i\) 来说，就有 左节点 \(2*i\)，右节点 \(2*i+1\)，而父节点就是 \(\frac i 2\)。

堆的操作

我们先介绍两种常用的堆操作：pop & push，添加一个元素和删除一个元素。

假如我们有如下的一个最大堆，当我们添加了一个元素之后，就需要做“堆化”，使得堆满足定义。

这种从堆底向上堆化的过程，叫做“从下到上堆化”。我把这个过程实现为代码，如下：

// 从下到上堆化
func (h *heap) downtoupheapify(pos int) {
    for pos / 2 > 0 && h.data[pos/2].less(h.data[pos]) { // 如果存在父节点 & 值大于父节点
        h.swap(pos, pos/2) // 交换两个值的位置
        pos = pos /2 // 将操作节点变为父节点的位置
    }
}

当我们想要从堆顶 pop 一个元素的时候。我们需要先将元素pop，然后把堆中最后一个元素放到堆顶，然后进行一次“堆化”。

这种从堆顶向下堆化的过程，叫做“从上到下堆化”。我把这个过程实现为代码，如下：

// 从上到下堆化
func (h *heap) uptodownheapify() {
    max := h.len
    i := 1
    pos := i
    for {
        if i * 2 <= max && h.data[i].less(h.data[i*2]) { // 如果有左子树，且自己小于左子树
            pos = i*2 
        }

        if i *2 +1 <= max && h.data[pos].less(h.data[i*2+1]) { // 如果有右子树，且自己小于右子树
            pos = i*2+1
        }
        if pos == i { // 如果位置没有变化，说明堆化结束
            break
        }

        h.swap(i, pos) // 交换当前位置和下一个位置的内容
        i = pos // 操作下一个位置
    }
}

golang 的 container.heap 包

注意，上述的讲述中，为了方便表示，我们在数组的索引0没有存储内容，从索引1开始存储。

而 golang 的实现中，索引0 是存储了数据的。这样的话，每一个元素的左子树和右子树就分别变成了 \(2*i+1\) 和 \(2*i+2\)。

golang 的 container.heap 是一个实现了通用最小堆的包。任何数据集只要实现了其 interface 接口，即可使用这个包将其堆化，并进行一系列的操作。

type interface interface {
    sort.interface
  push(x interface{}) // 把元素添加到 len() 的位置
    pop() interface{}   // 删除并返回 len() - 1 的元素.
}

// sort.interface
type interface interface {
    // len is the number of elements in the collection.
    len() int
    // less reports whether the element with
    // index i should sort before the element with index j.
    less(i, j int) bool
    // swap swaps the elements with indexes i and j.
    swap(i, j int)
}

interface 的数据结构如上，要求实现 sort.interface 和 push pop 两个方法。

sort.interface 的定义，同样贴在了上面，主要是三个方法：

• len 返回数据集的长度；
• less 返回 index i 是否小于 index j；
• swap 交换 index i 和 j 的值；

接下来，我们看一下 push 操作：

func push(h interface, x interface{}) {
    h.push(x) // 向数据集添加一个元素
    up(h, h.len()-1) // 从下向上堆化
}

// 从下向上堆化的内容
func up(h interface, j int) {
  // h 表示堆，j 代表需要堆化的元素 index
    for {
        i := (j - 1) / 2 // 定义 j 的父 index
        if i == j || !h.less(j, i) { // 如果两个元素相等 或者 父元素小于当前元素
            break  // 堆化完成
        }
        h.swap(i, j) // 交换父元素和当前元素
        j = i // index 变为父元素的 index
    }
}

上面在 push 元素之后，做了 “从下到上”的堆化。

接下来，是 pop 操作：

// 返回堆顶的元素，并删掉它
func pop(h interface) interface{} {
  n := h.len() - 1 // 获取最终堆长度（去掉最后一个元素）
    h.swap(0, n)     // 交换堆顶和最后一个元素
    down(h, 0, n)    // 从上到下堆化
    return h.pop()   // 弹出最后一个元素
}

func down(h interface, i0, n int) bool {
    i := i0 // 堆顶 index
    for {
        j1 := 2*i + 1  // 左孩子 index
        if j1 >= n || j1 < 0 { // j1 大于堆长度 或 溢出
            break  // 堆化结束
        }
        j := j1 // j = 左孩子
        if j2 := j1 + 1; j2 < n && h.less(j2, j1) { 
      // j2 = 右孩子；j 小于堆长度 && 右孩子小于左孩子
            j = j2 // j = 2*i + 2 = 右孩子 
        }
    // 上面是从左右孩子选出小的那个，将 index 赋值给 j
    
        if !h.less(j, i) { // 如果 堆顶小于 j , 堆化结束
            break
        }
    
        h.swap(i, j) // 交换堆顶元素和 j
        i = j // 切换到下一个操作 index
    }
  
  // 返回 元素是否有移动
  // 此处是一个特殊设计，用来判断向下堆化是否真的有操作
  // 当删除中间的元素时，如果向下堆化没有操作的话，就需要再做向上堆化
    return i > i0 
}

golang 还提供了之前原理讲述中没有的方法： remove fix

• remove 是删除堆中指定元素，不一定是堆顶；
• fix 是当某一个元素的值有变化时，用来重新堆化；

func remove(h interface, i int) interface{} {
    n := h.len() - 1 // 堆的长度
    if n != i { // 如果不是堆顶
        h.swap(i, n) // 交换删除元素 和 最后一个元素
        if !down(h, i, n) { // 从上到下堆化
            up(h, i) // 如果没有成功，就从下岛上堆化
        }
    }
    return h.pop() // 弹出最后一个元素
}

func fix(h interface, i int) {
  // i 是值被改变的 index
    if !down(h, i, h.len()) {   // 从上到下堆化
        up(h, i) // 如果没有成功，就从下岛上堆化
    }
}

这里有一个内容需要注意，就是 remove 中， \(n = len() -1\) 来表示堆长度，而在 fix 则使用 \(n = len()\) 来表示。这是因为 remove 中，最后一个元素是要被删除掉，所以最终的堆长度是 \(len() - 1\)。

上面我们已经了解了 golang 中，对于一个堆的所有操作。只剩下最后一个方法：init，初始化一个数据集，变成堆。

func init(h interface) {
    n := h.len()  // n 是堆长度
  // i = 最后一个非叶子节点的 index； i >= 堆顶； index 自减
    for i := n/2 - 1; i >= 0; i-- {
    // 从当前节点开始，从上到下堆化
        down(h, i, n)
    }
}

根据堆的特性可知，叶子节点不可以从上到下堆化。所以，我们找到最后非叶子节点的索引值，从这里开始做堆化操作。

至此，container.heap 包中的内容就全部讲解完毕。了解了堆的原理之后，其实会发现并不难理解。

堆的应用

在堆排序中，就需要用到堆算法来将数据级堆化，然后一个个的弹出元素，以达到排序的目的。

堆也可以用于实现优先级队列。优先级队列在实际开发过程中有着广泛的应用。在很多时候，都可以用它来实现处理带优先级的事件，处理定时任务等等。