堆的操作：

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

堆的存储

堆是一个完全二叉树。

存储：使用一个一维数组存储，下标从 1 开始存。完全二叉树一般都用一维数组存储。

小根堆：每个点都小于等于左右儿子。

xx 的左儿子：2x2x

xx 的右儿子：2x+12x + 1

基础操作

down(x)

down(x): 把一个节点往下移动。需要与左右两个孩子比较，与小的孩子交换。时间复杂度与树的高度成正比，因此是 O(log(n))O(log(n))

up(x)

up(x): 把一个节点往上移动。只需与父节点比较，如果比父节点小，就与父节点交换。时间复杂度与树的高度成正比，因此是 O(log(n))O(log(n))

再来看堆的操作

插入一个数

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

求集合中的最小值

1
heap[1]

删除最小值

用堆的最后一个元素覆盖堆顶的元素。将最后一个元素删除。将堆顶元素下移。

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

*删除任何一个元素

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

down 和 up 只会执行一个，堆最后一个元素要么比第 k 个元素大，要么小。

*修改任何一个元素

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

例题

堆排序

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
35
36
37
38
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int n,m;
int h[N];
int sz;
void down(int u) {
    // 找出父节点与左右孩子中最小的节点，将父节点与值更小的孩子节点交换，然后递归处理
    int t = u;
    if(u*2<=sz && h[u*2]<h[t]) t = u*2;
    if(u*2+1<=sz&&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], h[u/2]);
    u/=2;
  }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &h[i]);
    sz = n;
    // 从最后一个非叶子节点 down 一遍完成建堆
    for(int i=n/2;i;i--) down(i);
    while(m--) {
        printf("%d ", h[1]);
        h[1] = h[sz--];
        down(1);
    }
    return 0;
}

模拟堆

难点在于需要维护第 k 个插入的元素对应的堆中的编号关系，还有反查关系，堆中的编号对应的元素是第几次插入的。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;
int ph[N], hp[N];
int sz;
int h[N];
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;
    if(u*2<=sz && h[u*2]<h[t]) t = u*2;
    if(u*2+1<=sz && h[u*2+1]<h[t]) t = u*2+1;
    if(u!=t) {
        heap_swap(u, t);
        down(t);
    }
}
void up(int u) {
    while(u/2&&h[u/2]>h[u]) {
        heap_swap(u/2,u);
        u/=2;
    }
}
int main () {
    int n, m=0;
    scanf("%d", &n);
    while(n--) {
        char op[10];
        int k, x;
        scanf("%s", op);
        if(!strcmp(op, "I")) {
            scanf("%d", &x);
            sz++;
            m++;
            // 第m个插入的元素对应堆中的元素编号
            ph[m] = sz;
            // 堆中的元素对应的插入次序编号
            hp[sz] = m;
            h[sz] = x;
            up(sz);
        } else if(!strcmp(op, "PM")) {
            printf("%d\n", h[1]);
        } else if(!strcmp(op, "DM")) {
            heap_swap(1, sz);
            sz--;
            down(1);
        } else if (!strcmp(op, "D")) {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, sz);
            sz--;
            down(k);
            up(k);
        } else {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}