数据结构和算法-go 实现堆

Runtoweb3 的个人博客 / 0 / 2 / 创建于 4年前 / 更新于 3年前

一种特殊的树，满足下面两个条件：

1.堆总是一棵完全二叉树（除了最后一层，其他都是满节点，最后一层先排左节点）

2.堆中某个节点的值总是大于等于（小于等于）其所有子节点的值。如果是大于等于情况就称为大顶堆，小于等于情况就是小顶堆。

完全二叉树适合用数组存储，因为下标为i的元素，它的左子树下标为2i,右子树下标为2i+1。父节点就是i/2的overflow。

建堆

堆是用数组存储的,而且0下标不存，从1开始存储，建堆就是在原地通过交换位置，达到建堆的目的。完全二叉树我们知道，如果最后一个元素的下标为n,则1到n/2是非叶子节点，需要自上而下的堆化（和子节点比较），n/2 +1 到n是叶子节点，不需要堆化。

插入一个元素

先插入的元素放到堆最后，然后和父节点比较，如果大于父节点，就交换位置，然后再和父节点比较，直到把这个元素放到正确的层。这种也叫自下而上的堆化。

删除一个元素

假如删除大顶堆的，删除最大的元素，然后再它的子节点找到第二大元素，放到堆顶。然后再第二大元素下一层寻找

堆排序

比如有n个数据，我们先把数据建堆，生成一个大顶堆，元素个数为n

获取堆顶数据（也就是最大元素），删除堆顶，并且把最后一个元素放到堆顶，然后堆化成（n-1)大顶堆,堆化的时间复杂度为LogN,底数是2

重复获取堆顶，堆化成（n-2）大顶堆。我们获取的数据就是从大到小的顺序。

堆的应用

应用1：优先级队列

合并n个有序小文件把n个有序的小文件的第一个元素取出，放入堆中，取出堆顶到大文件，然后再从小文件中取出一个加入到堆，这样就把小文件的元素合并到大文件中了。

应用2：用堆求 Top K（就是从一堆数据中找出前k大的数据）

a. 针对静态数据（数据不变）建立大小为K的小顶堆，遍历数组，数组元素与堆顶比较，比堆顶大，就把堆顶删除，并插入该元素到堆 b. 针对动态数据（数据不断插入更新的）在动态数据插入的时候就与堆顶比较，看是否入堆，始终维护这个堆，需要的时候直接返回，最坏O(n*lgK)

应用3：海量关键词搜索记录，求搜索次数topK

a.先用hashTable去重，并累加搜索次数

b.再建立大小为K的小顶堆，遍历散列表，次数大于堆顶的，顶替堆顶入堆（就是应用2的解法）

散列表很大时，超出内存要求

建立n个空文件，对搜索关键词求哈希值，哈希值对n取模，得到该关键词被分到的文件号（0到n-1）
对每个文件，利用散列和堆，分别求出topK，然后把n个topK（比如10个Top 20，200很小了吧）放在一起，出现次数最多的K（20）个关键词就是这海量数据里搜索最频繁的。

go实现大顶堆

type heap struct{
    m []int
    len int //堆中有多少元素
}

func main() {
    m := []int{0,9,3,6,2,1,7} //第0个下标不放目标元素
    h := buildHeap(m) //建堆，返回一个heap结构
    h.Push(50)
    h.Pop()
    fmt.Println(h.m)
}
/**
建堆，就是在原切片上操作，形成堆结构
只要按照顺序，把切片下标为n/2到1的节点依次堆化，最后就会把整个切片堆化
 */
func buildHeap(m []int) *heap{
    n := len(m)-1
    for i:=n/2; i>0; i-- {
        heapf(m, n, i)
    }
    return &heap{m,n}
}
func (h *heap)Push(data int) {
    h.len++
    h.m = append(h.m, data)//向切片尾部插入数据（推断出父节点下标为i/2）
    i := h.len
    for i/2 >0 && h.m[i/2]<h.m[i] { //自下而上的堆化
        h.m[i/2], h.m[i] = h.m[i], h.m[i/2]
        i = i/2
    }
}
/**
弹出堆顶元素，为防止出现数组空洞，需要把最后一个元素放入堆顶，然后从上到下堆化
 */

func (h *heap)Pop() int{
    if h.len < 1 {
        return -1
    }
    out := h.m[1]
    h.m[1] = h.m[h.len] //把最后一个元素给堆顶
    h.len--
    //对堆顶节点进行堆化即可
    heapf(h.m, h.len, 1)
    return out
}
//对下标为i的节点进行堆化， n表示堆的最后一个节点下标
//2i,2i+1
func heapf(m []int, n,i int) {
    for {
        maxPos := i
        if 2*i<= n && m[2*i] > m[i] {
            maxPos = 2*i
        }
        if 2*i+1 <=n && m[2*i+1] > m[maxPos] {
            maxPos = 2*i + 1
        }
        if maxPos == i { //如果i节点位置正确，则退出
            break
        }
        m[i],m[maxPos] = m[maxPos],m[i]
        i = maxPos
    }
}