乘风原创程序

  • Golang Heap 源码剖析
  • 2021/7/2 10:11:17
  • 堆原理解析

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

    最大堆和最小堆

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

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

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

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

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

    完全二叉树的存储方式

    对于二叉树来说,存储方式有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.interfacepush 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 包中的内容就全部讲解完毕。了解了堆的原理之后,其实会发现并不难理解。

    堆的应用

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

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