简介

堆是一种完全二叉树（从上到下，从左到右排列）这意味着它可以被储存到一个数组中，并且对任意一个节点 ii 都有左子节点为 2i2i，右子节点为 2i+12i+1，该数据结构还满足单调性，父节点一定大于（或小于）子节点，但同级的节点之间大小顺序是不确定的，这使它具有动态维护最值的能力。

当插入元素时，我们需要下滤操作来维持堆的单调性，具体操作流程如下：

  1. 将当前节点和两个子节点作比较，如果满足单调性不做任何调整。
  2. 如果不满足将较小的子节点与父节点交换，使较小的子节点在上面。
  3. 递归执行将放下去的大数继续下滤，直到满足单调性或者没有子节点为止。

由于操作次数最多为树的高度，所以这个操作的复杂度是 O(log⁡n)O(\log n)。对于一个无序数组，我们并不需要将元素逐个插入数组，这样会导致复杂度为 O(nlog⁡n)O(n\log n)。

事实上，将 位于1∼⌊n/2⌋1\sim\lfloor n/2 \rfloor 的元素下滤就可以使整个堆满足单调性，举几个特殊情况就可以说明这是正确的。接下来分析这个操作的时间复杂度（以下除法均为向下取整）

  1. 假设这是个满二叉树，那么倒数第一层会有 n/2n/2 个元素，倒数第 ii 层有 $ n/2^i$ 个元素。

  2. 从倒数第二层开始，到第一层结束，对于倒数第 ii 层最多下滤 i−1i-1 次。

  3. 树高 h=log2nh=log_2n，从倒数第二层到第一层就是 h−1=log2n−1h-1=log_2n-1。

  4. 所以操作次数如下：

    S=n22×1+n23×2+⋯=n(122+223+324+⋯ )2S=n(121+222+323+⋯ )⇒S=2S−S=n(12+122+123+⋯ )=n×12(1−(12)log⁡2n−1)1−12=n−2\begin{aligned} S&=\frac{n}{2^2}\times1+\frac{n}{2^3}\times2+\cdots\\ &=n(\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots)\\ 2S&=n(\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots)\\ \Rightarrow S&=2S-S\\ &=n(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots)\\ &=n\times\frac{\frac{1}{2}(1-(\frac{1}{2})^{\log_2n-1})}{1-\frac{1}{2}}\\ &=n-2\\ \end{aligned}

    注意，这里的 n-2 仅代表是满二叉树而且中间有各种取整操作，仅仅是一个理论值，没有什么实际意义，但是它可以说明这个操作的复杂度是 O(n)O(n)。

堆排序

下面以堆排序为例，记录堆在 C++ 中如何实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int h[N], sz = 0;

void down(int i) {
    // t 代表当前节点和两个子节点中最小的那个节点索引
    int t = i;
    if (i*2 <= sz && h[i*2] < h[t]) t = i*2;
    if (i*2+1 <= sz && h[i*2+1] < h[t]) t=i*2+1;
    if (t != i) {
        swap(h[t], h[i]);
        down(t);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", h+i);
    sz = n;
    
    for (int i = sz / 2; i; --i) down(i);
    
    while (m--) {
        printf("%d ", h[1]);
        h[1] = h[sz--];
        down(1);
    }
    return 0;
}

插入

插入元素时将元素添加到末尾，然后使用上滤操作将它交换到合适的位置。

1
2
3
4
5
6
7
8
void up(int i) {
    while (i / 2 >= 1 && h[i/2] > h[i]) swap(h[i/2], h[i]), i /= 2;
}

void insert(int x) {
    h[++sz] = x;
    up(sz);
}

修改与删除第k插入节点

要像静态链表那样记录下插入的位置，需要用到两个数组，ph 是从第 k 到堆中下标的映射，而 hp 是堆中下标到第 k 的映射，当我们交换两个元素时，如下图所示：

由于我们输入给 swap 的参数只知道堆中的下标，所以才需要 hp 这个数组储存下标对应的 k，然后交换 ph 中的这两个 k 对应的元素下标，随后再把 hp 对应的 k 交换。

这样的话，可以通过 ph[k] 正确地获取到第 k 插入元素的下标。至于这两个数组的名字，可以这样判断：ph 是从外部指向堆，而hp 是从堆指向外部。

相对应地，所有交换的操作都要用 heapswap 交换元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void heapswap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int k) {
    int t = k;
    if (k*2 <= sz && h[k*2] < h[t]) t=k*2;
    // 这里 h[t] 容易写成 h[k] 因为此时 t 可能等于 2k 所以必须写 h[t]
    if (k*2+1 <= sz && h[k*2+1] < h[t]) t=k*2+1;
    if (t != k) heapswap(t, k), down(t);
}

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

插入元素时要记得更新这两个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void insert(int x) {
    h[++sz] = x;
    ph[++idx] = sz, hp[sz] = idx;
    up(sz);
}

void remove(int k) {
    k = ph[k];
    heapswap(k, sz--);
    down(k), up(k);
}

void removetop() {
    heapswap(1, sz--);
    down(1);
}

void modify(int k, int x) {
    k = ph[k];
    h[k] = x;
    down(k), up(k);
}

动态维护最小值

实现一个数据结构，维护一个集合，给定 nn 个询问：

  1. 向集合中添加一个元素 xx。
  2. 删除集合中的元素 xx，为了方便造数据，不保证 xx 在集合中。
  3. 求出集合中的最小值，若不存在输出 −1-1。

显然可以用 multiset 做，并且 priority_queue 是不支持元素删除的，但是我们可以定义两个堆 p,qp,q 存储集合中的所有元素和被删除的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> p, q;

void add(int x) {
    p.push(x);
}

void erase(int x) {
    q.push(x);
}

int get() {
    while (p.size() && q.size() && p.top() == q.top()) p.pop(), q.pop();
    if (p.empty()) return -1;
    return p.top();
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0, x, tp; i < n; i++) {
        scanf("%d", &tp);
        if (tp == 1) scanf("%d", &x), add(x);
        else if (tp == 2) scanf("%d", &x), erase(x);
        else printf("%d\n", get());
    }
    return 0;
}

附数据生成程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <ctime>
#include <cstdio>
#include <random>
#include <algorithm>
using namespace std;

mt19937 rng(time(0));

int Rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int main() {
    int n = Rand(1e4, 1e6);
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) {
        int t = Rand(1, 3);
        if (t == 1) printf("1 %d\n", Rand(1, 1e9));
        else if (t == 2) printf("2 %d\n", Rand(1, 1e9));
        else printf("3\n");
    }
    return 0;
}