堆排序模板

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

down(int u)

void down(int u) {
    int t = u;
    if (2 * u <= nums && h[2 * u] < h[t]) t = 2 * u;
    if (2 * u + 1 <= nums && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    if (t != u) {
        swap(h[t], h[u]);
        down(t);
    }
}

up(int u)

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

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int h[N], nums;

void down(int u) {
    int t = u; //用t来表示这三个点里面的最小值标号
    if (u * 2 <= nums && h[u * 2] < h[t]) t = u * 2; //不要把h[t]写成h[1]！！！也不要写成h[u]
    if (u * 2 + 1 <= nums && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t); // down(t) 不是down(1) ！！！
    }
}

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) { //u/2>0只要有父节点且父节点比当前点的值大的话，那就说明需要调整，越小越上
        swap(h[u / 2], h[u]);
        u /= 2; //直到u/2==0为止
    }
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    nums = n; //这行代码一定得在下面的down(i)前执行，否则先执行down时，nums是0，错误
    for (int i = n / 2; i >= 1; i --) down(i); // 建堆这种建堆方式是O(N) 具体见P45
    while (m --) {
        printf("%d ", h[1]); //每次输出当前的堆顶元素
        h[1] = h[nums]; // 删除堆顶元素，把最后一个元素赋到堆顶（为什么是最后一个元素？因为一维数组删头难删尾易）
        nums --;
        down(1); //这里是down(1) ！！！
    }
    return 0;   
}