手写堆

STL中的priority_queue虽然用着舒服，但是不支持修改和删除操作，在某些问题上使用确实不太舒服。本文就是记录一下如何手写一个堆。

堆要满足的操作：（以小根堆为例，大根堆同理）

• 插入一个数
• 求集合当中的最小值
• 删除最小值
• 删除任意一个元素
• 修改任意一个元素

堆的结构

是一棵二叉树（完全二叉树）。
– 小根堆：父节点小于等于左右儿子
– 大根堆：父节点大于等于左右儿子

堆的存储

用一个一维数组来存储，下标从1开始。

堆的基本操作（以小根堆为例）

• down(x)：往下调整（把一个节点向下移），如果一个节点的值变大了，向下移动每次和左、右儿子中最小的进行交换。

• up(x)：向上调整。每次和父节点进行比较，如果比父节点小，则和父节点进行交换。

利用down和up操作可以拼出上述的5个操作。

用size表示堆的大小，heap表示堆（小根堆为例）
1. 插入一个数

heap[++size] = x; up(size);

2. 求集合中的最小值

heap[1];

3. 删除最小值

heap[1] = heap[size]; size--; down(1);

4. 删除任意一个元素

heap[k] = heap[size];
size--;
down(k);
up(k);

5. 修改任意一个元素

heap[k] = x;
down(k);
up(k);

讨论

如果我们通过插入操作来构建堆，可以发现若插入n个数，最坏O(n logn)

for(遍历n个点)
    插入第i个点

但若我们从倒数第二层的节点开始，从下到上做down操作，从 i = n / 2 开始，每次i–，时间复杂度为O（n）(挺好证明的)。

for(int i = n/2; i; i--)
    down(i);

int n, m;
int h[N], size;

void down(int 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);
    }
}

void up(int u)
{
    while(u / 2 && h[u/2] > h[u]) {
        swap(h[u/2], h[u]);
        u /= 2;
    }
}