声明一下：这里说的是如何手写一个堆，而不是$STL$

首先，堆的作用是维护一个数据集合，它可以实现以下操作：

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

这里面，前三个是堆的基本操作，后两个是$STL$里的堆无法直接实现的（当然手写的随意）。

怎么实现呢

其实堆使用一颗完全二叉树实现的

这里拿小根堆举例，小根堆就是每一个点都小于等于自己的子节点（大根堆相反）。
那么就可以知道，根节点就是最小的。

那么怎么存储呢

凡是跟二叉树有关系的，基本上都是用数组模拟的，可以让一号点当根节点，每个节点$a_i$的左节点就是$a_2i$，右节点是$a_2i+1$，这样就可以用一个一维数组存下来一个堆了。

代码：

堆有两个基本操作，$down$和$up$，意思分别是往下调整和往上调整

就上面说的那五个操作用$up$和$down$都能完成

先来看都怎么完成吧

我们用size来存储堆的大小，heap就是这个堆。

第一个操作：

heap[++size] = x; // 存入
up(size); // 一直往上找到合适的位置

第二个操作：

heap[1] 就是

第三个操作：

heap[1] = heap[size]; // 把第一个点变成最后一个点
size--; // 把最后一个点删除
down(1); // 把第一个点往下移

第四个操作：

heap[k] = heap[size];
size--;
up(k);
down(k); // 跟第三个操作差不多

第五个操作：

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

具体来说，往下调整的意思就是把一个节点往下移到他合适的位置，先思路，后模版：

主要就是每次跟自己的子节点比较一下，如果他不是最大的就交换（拿小根堆举例）

void down(int u){
    int t = u； // 用t表示三个点里面的最小值
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2；
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; // 这时候t就等于三个点里的最小值
    if (u != t){
        swap(h[u], h[t]);
        down(t);
    }
}

往上调整的意思就是把一个节点往上移到他合适的位置：

主要就是每次跟自己的父节点比较一下，如果他不是最小的就交换

void up(int u){
    while (u / 2 && h[u / 2] > h[u]){ 如果u不是根节点且比他爹小，就交换。
        swap(h[u], h[u / 2]);
        u /= 2;
    }
}

然后其他都是自己变化了。