模板
集合的插入输出删除都用到堆，插入一个数，删除一个数，修改一个数，输出最小值

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

注意：
1. ph[m] = cnt表示第 m 个插入的数的下标是 cnt，hp[cnt] = m表示下标是 cnt 的数是第 m 个插入的数//反函数
2. heap_swap(a,b)表示交换 h[a] 和 h[b],并维护 ph 和 hp 两个数组
3. 删除第 k 个数时，需要提前把第 k 个数的下标存储起来
// 交换两个点，及其映射关系
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 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && 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] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

如何手写一个堆？完全二叉树 5个操作  都用堆中的下标
1. 插入一个数         heap[ ++ size] = x; up(size);//先插入最下面然后进行up操作
2. 求集合中的最小值   heap[1]
3. 删除最小值         heap[1] = heap[size]; size -- ;down(1);//最大值替换最小值，然后down
4. 删除任意一个元素   heap[k] = heap[size]; size -- ;up(k); down(k);
5. 修改任意一个元素   heap[k] = x; up(k); down(k);
堆用一维数组存储，x 2x左孩子，2x+1右孩子；
堆的基本结构
堆是一颗二叉树
完全二叉树
小根堆：每个点都小于它的左右儿子

堆的存储
用一个一维数组来存 //完全二叉树

！！！线段树！！！
根节点[1][2][3][4][5][6][7][8][9][10][11][12][13][14]
                   1
            2                  3
        3         4        5          6
    7      8    9   10   11  12   13     14
x的左儿子：2x
x的右儿子：2x+1
x小于他的左右儿子，所以x=1最小的（下标从1开始）
越往下越大

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

“I x”，插入一个数x；
“PM”，输出当前集合中的最小值；
“DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；
“D k”，删除第k个插入的数；
“C k x”，修改第k个插入的数，将其变为x；
现在要进行N次操作，对于所有第2个操作，输出当前集合的最小值。

输入格式
第一行包含整数N。

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

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

每个结果占一行。

数据范围
1≤N≤105
−109≤x≤109
数据保证合法。

输入样例
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例
-10
6

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 1e5 + 10;

int h[N];           /* 堆                                                   */
int ph[N];          /* 存储第k个插入的数在堆中的下标   cin>>m>>x;ph[m]=cnt;hp[cnt]=m;h[cnt]=x 
int hp[N];          /* 存储堆中指定下标的值是第k个插入的数,与ph[N]互逆      */
int cnt;            /* 存储当前堆中用到了哪个下标,用于插入与删除等操作 就是总数，和下面例题s一样     */
//第m个操作插入x的数值，ph[m]=cnt;记录下标，hp[cnt]=m;反推，h[cnt]=x,堆中下标用cnt记录
void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]); /* 1.先通过下标a找到h[a]在堆中是第几个插入的数
                                   2.再通过第几个插入的数k找到在ph中所记录的在
                                    堆中对应的下标 3.最后与b交换            */
    swap(hp[a], hp[b]);         /* 交换所记录的在堆中插入的值的顺序         */
    swap(h[a], h[b]);           /* 交换堆中的值                             */
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) 
        t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) 
        t = u * 2 + 1;

    if (u != t)                 /* 如果u不是当前以u为根节点的堆的最小值     */
    {
        heap_swap(u , t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2]) {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    cin >> n;
    while (n--) {
        string op;
        int k, x;
        cin >> op;
        if (op=="I") {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt;    /* 堆中第m个插入的数在堆中的下标是cnt   */
            hp[cnt] = m;    /* 堆中下标为cnt的数是在堆中是第m个插入的   */
            h[cnt] = x;//h[]来存储，h[cnt]=x;在下标为cnt的堆里面h[cnt]来存储
            up(cnt);//插入在最下面只进行up操作
        }
        else if (op=="PM")//输出最小值h[1]
            cout << h[1] << endl;
        else if (op=="DM") {//删除最小值，用最大值来交换，在删除最后一个堆（交换后的最小值）
            heap_swap(1, cnt);
            cnt --;
            down(1);//down一下
        }
        else if (op=="D") {
            cin >> k;
            k = ph[k];                  /* 取得第k个插入的数在堆中的下标        */
            heap_swap(k, cnt);
            cnt --;
            up(k);//二选一
            down(k);
        }
        else if (op=="C") {//修改
            cin >> k >> x;
            k = ph[k];//查下标
            h[k] = x;
            up(k);
            down(k);
        }

    }

    return 0;
}

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

输入格式
第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

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

数据范围
1≤m≤n≤105 1≤m≤n≤105，
1≤数列中元素≤1091≤数列中元素≤109
样例
输入样例:

5 3
4 5 1 3 2
输出样例:

1 2 3

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int h[N];
int n, m, s;

void down(int u) {
    int t = u;
    if (2 * u <= s && h[2 * u] < h[t]) t = 2 * u; // 比较左儿子
    if (2 * u + 1 <= s && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 比较右儿子
    if (t != u) {
        swap(h[t], h[u]); // 交换数值
        down(t); // 递归调用
    }
}

int main() {
    cin >> n >> m;
    s = n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = n / 2; i; --i) down(i); // O(n)时间建堆
    while (m--) {
        cout << h[1] << " ";
        // 删除最小值操作
        h[1] = h[s];
        s--;
        down(1);
    }

    return 0;
}