堆排序：

堆：完全二叉树

小根堆：每个节点的根节点的值最小，以此类推构成的堆就是小根堆，将一个数组构造成小根堆，每一次取祖宗节点，可以进行堆排序

如何手写一个堆？

1.在堆中插入一个数：heap[ ++ size] = x, up(size)

2.求当前集合中的最小值：heap[1]

3.删除最小值：head[1] = heap[size], size -- , down(1)

4.删除任意一个元素：heap[k] = heap[size], size -- , down(k), up(k)

5.修改任意一个元素：heap[k] = x, down(k), up(k)

down()操作：

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) {
        swap(h[u], h[t]);
        down(t);
    }
}

up()操作：

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

将数组构造成小根堆：

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

堆排序实际上只需要输出最小值和删除最小值的操作即可完成。

堆排序代码：

#include<iostream>

using namespace std;

const int N = 100010;

int n, m;

int h[N];

int size;

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) { //根节点不是最小值
        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]);
    size = n;
    for (int i = n / 2; i; i --) down(i);
    while(m -- ){
        printf("%d ", h[1]);
        h[1] = h[size];
        size -- ;
        down(1);
    }
    return 0;
}