堆 : 完全二叉树
小顶堆 : 父节点一定小于或等于左右儿子
大顶堆 : 父节点一定大于或等于左右儿子
用数组存储 : 根节点是1,左儿子是2x,右儿子是2x+1
如果要求排序为升序,一般采用大顶堆,每次将堆顶元素与未排序的最后一个元素交换,再调整堆
如果要求排序为降序,一般采用小顶堆,每次将堆顶元素与未排序的最后一个元素交换,再调整堆

步骤 : (假设为升序)
1.将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点
2.将其与末尾元素进行交换,此时末尾就为最大值
3.然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值,然后递归执行
便能得到一个有序序列了

如果将一个无序序列构造成一个大顶堆 : 
从最后一个父节点开始调整,如果他不是最大值且其左右儿子比他大,交换他们两个的位置
(先交换左儿子),从右至左,从下至上(即倒序调整),然后递归即可

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int n,m;
int r;   //保存堆的元素个数
void down(int u)   //调整无序序列
{
    int t=u;   //记录最小值的编号(目前父节点的编号)
    if (2*u<=r&&a[2*u]<a[u]) t=2*u;   //有左儿子,并且左儿子比t节点的值小,更新t
    if (2*u+1<=r&&a[2*u+1]<a[t]) t=2*u+1;   //有右儿子,并且右儿子比t节点的值小,更新t
    if (u!=t)   //如果目前的父节点不是最小值
    {
        swap(a[u],a[t]);   //和儿子节点进行交换
        down(t);
    }
}
int main()
{
    cin>>n>>m;
    r=n;   //开始时,堆中的元素数量为n
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i = n /2 ; i >= 1; i--) down(i);   //从最后一个父节点开始调整
    while (m--)
    {
        cout<<a[1]<<" ";   //输出堆顶,即最小值
        swap(a[1],a[r]);   
        r--;   
        down(1);
        //交换堆顶和堆尾,并对剩下的n-1元素进行重新排序
    }
}