手写堆操作

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(x)

基本操作

void down(int u){
    int t = u;
    if(2 * u <= hsize && h[t] > h[2 * u]) t = 2 * u;
    if(2 * u + 1 <= hsize && h[t] > h[2 * u + 1]) t = 2 * u + 1;
    if(t != u){
        swap_heap(t, u);
        down(t);
    }
}

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

主要应用

堆排序
模拟堆