$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
堆是二叉树的结构，我们要利用堆实现以下五个操作：
1. 插入一个数
2. 求集合最值
3. 删除最值
4. 删除任意元素
5. 修改任意元素

前三个操作可以采用STL直接实现，然而后两个就不行了。

堆删除最后一层之后是一个完全二叉树，我们以小根堆为例。

如何存储？

我们以下标作为编号，编号为$1$的是根节点，随后用父子2倍表示法，也就是$x$的左儿子是$2x$，右儿子是$2x+1$。

小根堆的堆顶是$Min$。

我们来看一下$heap$的两种基本操作$up$和$down$。

1. $down(x)$ 往下移：$x$本身与$x$的两个儿子中更小的交换，直到无法交换。
2. $up(x)$ 往上移：$x$本身与$x$的父节点更小的交换，直到无法交换。

接下来是操作的实现。

我们设$heap$数组就是编号数组。
$insert(x)$：

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

$query$

return heap[1];

$delete$

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

$del(k)$

heap[k] = heap[size];
size--;
down(k); up(k);   //干脆up和down一起执行，因为毕竟这只会选择其中一个执行。

$change(k,x)$

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

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, h[N], sz = 0;
int 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);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    sz = n;
    for (int i = n / 2; i ; i--) down(i);  //O(n)建堆
    while (m--) {
        printf("%d ", h[1]);
        h[1] = h[sz]; sz--;
        down(1);
    }
    return 0;
}