---

一、堆的数据结构

堆是一个完全二叉树：除了最后一层结点以外，上面的每一层都是满的。最后一层的结点是从左到右排布的。

小根堆：每一个点都是小于左右子节点的，所以根节点就是树中最小值或者叫小顶堆。(递归定义)

存储方式：全新的存储方式，用一维数组来存。因为是完全二叉树，所有数据的下标是有规则可以找到的。

• 父节点x/2
• 节点x
• 左子节点2x
• 右子节点2x+1

注意下标从1开始的（符合节点之间的数学规律）

二、堆的操作方法

往下调整的示意图

down(x) 往下调整

往上调整的示意图

up(x) 往上调整

相关功能的实现思路

1.插入一个数

heap[++size] = x;
up(sz); // 往上调整

2.求最小值

heap[1];

3.删除最小值

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

4.删除任意一个元素

heap[k] = heap[sz--];
// 只执行其中之一 ：大了向下走  小了向上走
down(k);
up(k);

5.修改任意一个元素

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

三、堆的实战运用

堆排序

题目描述：
输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。

输入格式：
第一行包含整数 $n$ 和 $m$。第二行包含 $n$ 个整数，表示整数数列。

输出格式：
共一行，包含 $m$ 个整数，表示整数数列中前 $m$ 小的数。

数据范围：
$1\le m\le n\le 10^5$

$1\le$ 数列中元素 $\le 10^9$

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

tip：

当建树时应从$n/2$的位置开始向上进行down(x)操作，因为根节点无需往下调整，同时其时间复杂度为$O(n)$。

由于根节点为堆的最小值，所以最后询问操作时，打印一次堆最小值，同时删除。

除此之外使用 for (int i = 1; i <= n; i++) up(i);时间复杂度为$o(nlogn)$的这种方法也是可以的。

由于堆为完全二叉树，其高度为 $lo{g}_{2}n$层，递归版的down(x)的时间复杂度为$o(logn)$，所以没必要将down(x)改为循环。

代码实现：

const int N = 1e5 + 10;
int h[N], cnt;
void down(int x)
{int t = x;// 注意此处不能使用else if// 每次左右子节点要分别进行一次条件判定if (x * 2 <= cnt && h[x * 2] < h[t]) t = x * 2;if (x * 2 + 1 <= cnt && h[x * 2 + 1] < h[t]) t = x * 2 + 1;if (x != t){swap(h[x], h[t]);down(t);}
}
int main()
{cin.tie(0);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> h[i];cnt = n;for (int i = n / 2; i > 0; --i) down(i); //建树，从倒数第二层开始建，然后向上while (m--){cout << h[1] << ' ';h[1] = h[cnt--];down(1);}return 0;
}

tip：
up(x)的基础操作：

①循环

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

②递归

void up(int x)
{if(x / 2 && h[x / 2] > h[u]){swap(h[x / 2], h[x]);up(x / 2);}
}

down(x)循环版本:

void down(int i) {while ((i << 1) <= sz) {int t = i << 1;if (t + 1 <= sz && h[t] > h[t + 1]) t ++;if (h[t] >= h[i]) break;swap(h[t], h[i]);i = t;}
}

模拟堆

题目描述：

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x，插入一个数 $x$；
2. PM，输出当前集合中的最小值；
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. D k，删除第 $k$ 个插入的数；
5. C k x，修改第 $k$ 个插入的数，将其变为 $x$；

现在要进行 $n$ 次操作，对于所有第 $2$ 个操作，输出当前集合的最小值。

输入格式：
第一行包含整数 $n$。

接下来 $n$ 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式：
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围：
$1\le n\le 10^5$

$-10^9\le x\le 10^9$

数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

难点：
要找到第 $k$ 个插入的数，因为插入后会进行上下调整，要额外开辟数组，来储存第 $k$ 个插入的数在堆中的位置。

代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;const int N = 1e5 + 10;// h代表heap（堆），ph（point->heap）可以获得第几个插入的元素现在在堆的那个位置
// hp(heap->point)可以获得在堆的第n个元素存的是第几个插入的元素
int h[N], ph[N], hp[N], cnt;void heap_swap(int a, int b)
{// 根据a和b的位置找到它们分别是第几个插入的元素，然后将其（在h数组中的）下标转换swap(ph[hp[a]], ph[hp[b]]);// 将两个位置存的是第几号元素转换swap(hp[a], hp[b]);// 最后再转换值(这三个语句位置可以换，但是从上到下逐渐变短的话比较美观)swap(h[a], h[b]);
}
void down(int x)
{int t = x;if (2 * x <= cnt && h[2 * x] < h[t]) t = 2 * x;if (2 * x + 1 <= cnt && h[2 * x + 1] < h[t]) t = 2 * x + 1;if (t != x){heap_swap(x, t);down(t);}
}
void up(int x)
{while (x / 2 && h[x] < h[x / 2]){heap_swap(x, x / 2);x >>= 1;}
}int main()
{cin.tie(0);int n, m = 0;cin >> n;while (n--){string s;int k, x;cin >> s;if (s == "I"){cin >> x;cnt++;m++;ph[m] = cnt, hp[cnt] = m;h[cnt] = x;up(cnt);}else if (s == "PM") cout << h[1] << endl;else if (s == "DM"){heap_swap(1, cnt);cnt--;down(1);}else if (s == "D"){cin >> k;k = ph[k];heap_swap(k, cnt);cnt--;up(k);down(k);}else if (s == "C"){cin >> k >> x;k = ph[k];h[k] = x;up(k);down(k);}else cout << "error" << endl;}return 0;
}