堆的原理

• 堆是一个完全二叉树

• 小根堆：父亲比左右儿子小，根节点是最小值
  小根堆：父亲比左右儿子大，根节点是最大值

• 编号$x$的左儿子：$2x$，右儿子：$2x+1$
  下标从1开始

---

堆的操作

堆的操作主要有两种：down、up

以小根堆为例：

down：如果编号$x$如果变得比儿子大，则和较小的儿子进行交换，直到放到合适的位置（两儿子都比它大）。
up：如果编号$x$如果变得比父亲小，则和父亲交换，直到放到合适的位置（比父亲大）。

// 注意输入的u要合法，不能大于size
void up(int u) {while (u > 1 && heap[u] < heap[u / 2]) swap(heap[u], heap[u / 2]), u /= 2;
} 
// 注意输入的u要合法，不能等于0
void down(int u) {int t = u;while (true) {if (u * 2 <= size && heap[u] > heap[u * 2]) t = u * 2;if (u * 2 + 1 <= size && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;if (u != t) {swap(heap[u], heap[t]);u = t;}else break;}
}

1. 插入一个数
   堆末尾添加一个数，并调整
   heap[ ++ size ] = x;
up(size);
2. 求集合中最小值
   就是堆顶
   head[1]
3. 删除最小值
   用堆末尾替换堆顶，再调整
   head[1] = head[ size -- ];
down(1);
4. 删除任意一个元素
   head[k] = head[size -- ]
down(k)
up(k)
5. 修改任意一个元素
   heap[k] = x
down(k)
up(k)
6. 建立堆
   for (int i = 1; i <= n ; i ++ ) head[i] = a[i]; 先给haep随便赋值
   for (int i = n / 2; i ; i -- ) down(i); $O(n)$时间进行建堆
   因为最后一层的$n/2$个点都没有孩子，所以不需要down，故$i$从$n/2$开始
   倒数第二层有$n/4$个点，最多需要down 1次
   倒数第三层有$n/8$个点，最多需要down 2次
   倒数第四层有$n/16$个点，最多需要down 3次
   …
   …
   $$1\ast \frac{n}{4}+2\ast \frac{n}{8}+3\ast \frac{n}{16}+...$$
   $$=n(\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\frac{4}{2^5}+...)$$
   令S
   $$S=\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\frac{4}{2^5}+...$$
   左右乘2
   $$2S=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}+\frac{5}{2^5}+...$$
   上面两式相减
   $$2S-S=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+...$$
   $$S=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\frac{1}{2^5}+...<1$$
   因此该操作次数小于n，是$O(n)$的。

---

基本的堆

题目链接

#include <iostream>
#include <cstring>
using namespace std;const int N = 1000005;
int heap[N], size;
int n;void up(int u) {while (u > 1 && heap[u] < heap[u / 2]) swap(heap[u], heap[u / 2]), u /= 2;
} void down(int u) {int t = u;while (true) {if (u * 2 <= size && heap[u] > heap[u * 2]) t = u * 2;if (u * 2 + 1 <= size && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;if (u != t) {swap(heap[u], heap[t]);u = t;}else break;}
}int main() {scanf("%d", &n);int op;int k, x;while (n -- ) {scanf("%d", &op);if (op== 1) {scanf("%d", &x);heap[ ++ size] = x;up(size);}else if (op == 2) {printf("%d\n", heap[1]);}else {heap[1] = heap[size -- ];down(1);}}return  0;
}

---

带映射堆（可对第k个插入元素操作）

注意这题需要保存第k个插入的数在堆中的映射，同时也要保存堆到第k个插入的数的映射。
因此交换操作和删除操作，也要对这个映射进行操作。

#include <iostream>
#include <cstring>
using namespace std;const int N = 100005;
int heap[N], size_heap;
int n;
int hp[N]; // 堆 到 第k个插入元素 的 映射 
int ph[N]; // 第k个插入元素 到 堆 的映射 void heap_swap(int a, int b) {swap(heap[a], heap[b]);swap(ph[hp[a]], ph[hp[b]]);swap(hp[a], hp[b]);
}void up(int u) {while(u > 1 && heap[u] < heap[u / 2]) heap_swap(u, u / 2), u /= 2;
}void down(int u) {int t = u;while(true) {if (u * 2 <= size_heap && heap[u] > heap[u * 2]) t = u * 2;if (u * 2 + 1 <= size_heap && heap[t] > heap[u * 2 + 1]) t = u * 2 + 1;if (u != t) {heap_swap(u, t);u = t;}else break;}
}int main() {scanf("%d", &n);char op[2];int k, x, cnt = 0;while(n -- ) {scanf("%s", op);if (op[0] == 'I') {scanf("%d", &x);heap[ ++ size_heap] = x;hp[size_heap] = ++ cnt;ph[cnt] = size_heap;up(size_heap);}else if (!strcmp(op, "D")) {scanf("%d", &k);k = ph[k];//heap[k] = heap[size_heap -- ]; // 错的，还要对映射操作heap_swap(k, size_heap -- );up(k);down(k);}else if (!strcmp(op, "C")) {scanf("%d%d", &k, &x);k = ph[k];heap[k] = x;up(k); down(k);}else if (!strcmp(op, "PM")) {printf("%d\n", heap[1]);}else if (!strcmp(op, "DM")) {//heap[1] = heap[size_heap -- ]; // 错的，还要对映射操作heap_swap(1, size_heap -- );down(1);}}return 0;
}