堆维护一个数据集合

堆的基本操作

1.插入一个数

// 在堆的最后一个位置插入x然后up向上调整
heap[++size] = x;  
up(x);

2.求集合中的最小值

heap[1];

3.删除最小值

// 用堆的最后一个元素覆盖堆顶元素,然后down向下调整
heap[1] = heap[size]; // 覆盖
size--; // 删除最后一个
down(1);  // 向下调整

4.删除任意元素

heap[k] = heap[size]; // 用最后一个元素覆盖第k个元素
size--; // 删除最后一个
// up和down只会执行一个(分类)
down(k);
up(k);

5.修改任意元素

heap[k] = x;
// up和down只会执行一个(分类)
down(k);
up(k);

小根堆：
每个结点的值都小于左右子结点( 根结点为树的最小值 )

堆的存储：
堆用一个数组来存储( 下标从1开始 )
h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1

// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
// size表示当前堆的大小
int h[N], ph[N], hp[N], size;
ph[j] = k, hp[k] = j;
// 交换两个点，及其映射关系
void heap_swap(int a, int b) {
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}
// 若一个值变大了需要向下调整
void down(int u) {
    int t = u;
    // t 存储3个结点中最小的结点编号
    //2 * u存在且h[t] 比左儿子 h[u * 2]大
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    //2 * u + 1存在且h[t] 比右儿子 h[u * 2 + 1]大
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    // u != t, 说明根结点不是最小值
    if (u != t)
    {
        heap_swap(u,t);
        down(t);
    }
}
// 若一个值变小了需要向上调整
void up(int u) {
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
// i 从 n/2 down 到 1;
for (int i = n / 2; i; i -- ) down(i);