数据结构：堆、哈希表与字符串哈希详解

堆

如何手写一个堆？

1. 插入一个数
2. 求集合当中的最小值
3. 删除最小值
4. 删除任意一个元素
5. 修改任意一个元素

堆的结构：是一个完全二叉树（除了最后一层节点，其余节点都是非空的，最后一层是从左到右依次排布）。 小根堆：每个根都是小于它的两个子节点的。 大根堆：每个根都是大于它的两个子节点的。

堆的存储

凡是堆状，完全二叉树都是这样存的，拿一个数组存储。

堆有两个基本操作

这两个操作完全可以组合，然后把上面提到的五个操作完成。

1. down(x)

是把一个节点往下移，就比如下面这个图，我们找到不合适的位置，然后对他进行 down，我们找到左右子节点最小的那个进行交换。

void down(int u){ //u 是索引哈，是第几个节点，h[u] 就是这个节点的值
    int t = u; 
    //判断有没有左儿子，如果有并且左儿子小于这个值
    if(u*2 <= size && h[u * 2] < h[t]) t = u * 2;
    //同理
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

2. up(x)

和 down 反着来，同理就行。

void up (int u){ 
    //看父节点就行了
    while(u / 2 && h[u / 2] > h[u]) { 
        swap(h[u/2], h[u]); 
        u/=2; 
    } 
} 

操作一：插入一个数

我们用 size 表示堆的大小，heap 表示我们这个堆。 heap[++size] = x; up(size); 我们就是在堆的最后一个位置插入 x，然后进行上移。