本笔记内容来源于算法基础课

堆

方便讨论，本文一般讨论最小堆

最小堆模拟提供的操作：

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

堆是一棵完全二叉树，只有叶节点所在的层存在空节点，叶节点层节点从左到右排列

性质：任意一个节点都小于等于左右子节点

由性质可得，对于任意一棵子树，它的根节为此棵树的最小值

堆的存储

h[i] 代表节点i的值，下标从1开始

x的左子节点为2*x，x的右子节点为2*x+1

堆的调整

向下调整

当堆中的一个元素值变大，它需要向下调整，也称为“下沉”

与两个子节点进行比较，然后决定下沉方向，直至满足堆性质

void down(int u) {
    int p = u; // p代表给定节点与左右儿子中的最小元素的下标
    if (u * 2 <= size && h[u * 2] < h[p]) p = u * 2; // 左儿子存在且小于给定节点，p移动到左儿子
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[p]) p = u * 2 + 1; // 右儿子存在且小于给定节点和左儿子，p移动到右儿子
    if (p ! = u) { // 左右儿子存在更小元素
        int t = h[p]; h[p] = h[u]; h[u] = h[t]; // 与最小元素交换元素
        down(p); // 对儿子节点进行递归
    }
}

向上调整

当堆中的一个元素值变小，它需要向下调整，也称为“上浮”

与父点进行比较，不断上浮，直至满足堆性质

void up(int u) {
    while (u / 2 >= 1 && h[u / 2] > h[u]) { // 父节点存在且大于给定节点
        int t = h[u / 2]; h[u / 2] = h[u]; h[u] = t; // 交换元素
        u /= 2; // 移动到父节点
    }
}

堆的操作

建堆

1. 不断插入，时间复杂度为$O(nlgn)$
2. 从最后一个叶节点的父节点到根节点向下调整，时间复杂度为$O(n)$

证明：
从尾节点为$n$，则父节点为$\frac{n}{2}$，该层包含$\frac{n}{4}$个元素，树的高度为$1$，依次类推到根节点
$\frac{n}{4} \times 1 + \frac{n}{8} \times 2 + \cdots$
$= n(\frac{1}{2^2} + \frac{2}{2^3} + \cdots) < n$
右项为等差数列乘上等比数列，可以化简

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

向堆插入一个数

void insert(int x){
    h[++size] = x; // 插入新的尾节点
    up(size); // 向上调整
}

求集合中的最小值

heap[1];

因为删除尾节点非常方便

删除最小值(根节点)转换为：调整根节点值为尾节点，删除尾节点，下沉根节点

void removeRoot() {
    h[1] = h[size];
    size--;
    down(1);
}

删除任意一个节点转换为：调整节点值为尾节点，删除尾节点，若节点值变大（下沉）节点值变小（下浮）

void remove(int k) {
    h[k] = h[size];
    size--;
    down(k);
    up(k); // up(k), down(k)仅会执行其中一个
}

修改任意一个元素：若节点值变大（下沉）节点值变小（下浮）

void set(int k) {
    h[k] = x;
    down(k);
    up(k);
}

扩展

若要操作第k个插入的数，则需要额外维护两个数组：
ph[k]第k个插入的数在堆中的下标
hp[k]堆中第k个数是第几个插入的数，从而使得在交换元素时能获得对应的ph

可将其视为一个双向链表中的两个节点

void heap_swap(int a, int b) {
    int t;
    t = ph[hp[a]]; ph[hp[a]] = ph[hp[b]]; ph[hp[b]] = t;
    t = hp[a]; hp[b] = hp[a]; hp[a] = t;
    t = h[a]; h[a] = h[b]; h[b] = t;
}

在调整时需要调用heap_swap,而在删除操作也需要先调用heap_swap再调用size--

void remove(int k) { // 删除第k个插入的数
    int u = hp[k]; // 需要记录调整的下标
    heap_swap(hp[k], size);
    size--;
    up(u);
    down(u);
}

习题

Acwing 4072 延迟删除