Golang heap完全解析

heap.Interface是go基础库中提供的一个实现堆功能的工具包。本文将介绍如何使用以及它底层的算法实现
本质上说,堆就是一种特殊的二叉树。它总是满足下列性质:
  • 堆中某个节点的值总是不大于或不小于其父节点的值;(前者为最大堆,或者为最小堆,本文为了叙述方便,后面涉及的所有默认为最大堆)。
  • 堆总是一棵完全二叉树。
通常(包括go中)我们使用数组来实现堆,此时它还包含以下特性(事实上是二叉树的特性):
  • arr[0~n]数组保存堆
  • arr[0]为堆顶
  • arr[i]的左子节点为arr[i*2+1]
  • arr[i]的右子节点为arr[i*2+2]
  • arr[i]的父节点为arr[(i-1)/2]
堆在数组中的结构

使用

heap提供以下几个方法出来,实现对用户定义的堆结构h的基础操作:
  • Init(h Interface) //初始化堆h,完成第一轮的排序,使最大值落在堆顶
  • Push(h Interface, x interface{}) //将值推入堆h
  • Pop(h Interface) interface{} //从堆h顶弹出一个元素(即最大值)
  • Remove(h Interface, i int) interface{} //从堆h中移除下标为i的元素
可以看到这里使用的堆结构是Interface接口,它定义如下:
package heap
type Interface interface {
    sort.Interface
    Push(x interface{})// 将元素推入Interface
    Pop() interface{}  // 从Interface中弹出一个元素
}
//heap.Interface接口又继承了sort.Interface接口,它的如下
type Interface interface {
    // 返回结构中元素的总数
    Len() int
    // 判断下标为i的元素是否比下标j的元素小
    Less(i, j int) bool
    // 交换下标为i与j的元素位置
    Swap(i, j int)
}
千万要注意heap直接暴露的方法Push和接口中定义的Push,这是两个方法。

所以当我们需要将一个对象(通常继承自数组)当做堆来使用时,需要该对象实现上述的5个方法。比较简单,下面将官方demo的代码贴上来参考。
// This example demonstrates an integer heap built using the heap interface.
package main

import (
    "container/heap"
    "fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h)
    heap.Push(h, 3)
    fmt.Printf("minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

原理解析

使用上很简单,着重来看看它是如何实现的。也就是heap中的几个方法,Init(),Push(),Pop(),etc.

Init(h Interface)

init方法做的事情是对h做第一次排序,但是注意!并不保证整个堆的有序。
func Init(h Interface) {
    n := h.Len()
    // n/2 - 1即最后一棵子树的顶点下标,并倒序遍历直到整棵树的顶
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)//将小值下沉,保证以i为顶点的子树中,最大值位于顶点(注意!但是整棵树并不一定是完全有序的)
    }
}

func down(h Interface, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1 //左子节点
        if j1 >= n || j1 < 0 { // 防溢出
            break
        }
        j := j1 //左子节点
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2 右子节点,将左右子节点的大值赋给j
        }
        if !h.Less(j, i) {//j比当前节点i小,即不需要操作,此树的最大点位于顶点。因为down()操作是从最后一个子树倒序遍历操作的,所以任何一个子树的最大值都可以位于顶点。
            break
        }
        h.Swap(i, j)//交换i与j
        i = j//下沉到子树中,继续操作
    }
    return i > i0
}
下面看看一棵具体的树的排列过程:
原始结构
从最后一棵子树开始操作
完成一棵子树后倒序遍历所有子树执行相同的操作,直到树顶
在子树内部也始终保证最大值在堆顶
因为遍历所有子树操作,所以时间复杂度是O(n)。

Pop(h Interface) interface{} & Push(h Interface, x interface{})

package heap
func Pop(h Interface) interface{} {
    n := h.Len() - 1 //最后的元素的下标
    h.Swap(0, n) //交换n和0位置上的元素
    down(h, 0, n) //对堆顶的元素进行down()操作,保证子树(即整棵树)有序。注意这里的n为len-1, 即排序时不会涉及最后一个元素(即最大的元素)。一轮down()操作之后最大的元素还在最后一个位置
    return h.Pop() //将最后一个元素弹出
}
package heap
func Push(h Interface, x interface{}) {
    h.Push(x) //调用堆对象的Push方法将新元素添加到最后
    up(h, h.Len()-1) //从最后一个元素开始调用up()方法,保证子树有序
}
func up(h Interface, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}
有心的同学或许发现,其实down和up的方法的效果是类似的。不同地方在于前者是遍历节点跟其子节点比较,后者是便利节点跟其父节点比较,但都是遇到不遵循父大子小关系的节点交换位置。同样,经过一轮up操作之后也无法保证整棵树的有序,仅仅能保证最大的节点经过up之后会位于堆顶。
在Init()和Push()的操作后,都无法保证整棵树的有序。但是通过把排序的操作分散在每一次的Init()、Push()也包括后面的Pop(),使得不会存在某一步的操作效率太低。
同样,我们来看看一颗具体的树是怎样做Pop()和Push()操作的(继续上面Init的结果):
Pop()操作:交换最后一个元素和堆顶的位置
Pop()操作:省略对除了7之外的元素的排序过程,弹出最后的一个元素,即最大的元素7
Push()操作:从尾部压入一个新元素4
Push()操作:倒序遍历所有元素,保证其不比父节点大。

发表评论

电子邮件地址不会被公开。

+ 44 = 54