基本原理：

利用数组模拟堆，模拟出的堆本质上是一棵完全二叉树，完全二叉树指的是从倒数第二层开始，每一个节点都是满的，并且最后一层是从左到右排列，这个二叉树比较特殊，其中存储的数据符合特定的规律，每个结点i的左下方子节点下标为2i，右子节点为2i+1，并且三个元素中，上方结点的值最小，所以堆顶元素是最小的，数值越大的越靠近下层，那么在实现堆排序时，只需把数组用堆存储好，再依次输出堆顶元素，就完成了堆排序。

实现过程：

读入数据，实现小根堆

cin>>n;
for(int i=1;i<=n;i++)
cin>>h[i];
for(int i=n/2;i;i--)
down(i);

实现down操作(利用递归反复在三个节点中比较，如果结点值大于子节点值，则交换两个数，直到满足小根堆的条件)

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

逐次输出顶部的根节点

while(m--)
{
    printf("%d ",h[1]);
    h[1]=h[cnt--];
    down(1);
}

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int h[N];
int n,m,cnt;
int main()
{
    cin>>n>>m;
    cnt=n;
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=n/2;i;i++)
        down(i);
    while(m--)
    {
        printf("%d ",h[1]);
        h[1]=h[cnt--];
        down(1);
    }
    r
}