算法1

思路：这是一道小根堆的题，小根堆就是叶子节点和他的父节点比较，如果小于父节点，上移，建议把down()函数背过，我们输入一组数，

down()-将小数上移

void down(int u)
{

    int t=u;//t表示根节点和他左右儿子，这三个点的最小值
    //如果有左儿子，并且左儿子小，让左儿子上移
    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)//如果当前根节点不是最小的那个数，就交换
    {
        swap(h[u],h[t]);
        down(t);
    }
}

C++ 代码

#include<iostream>

using namespace std;
const int N=100010;

int n,m;
int h[N],cnt;
void down(int u)
{

    int t=u;//t表示根节点和他左右儿子，这三个点的最小值
    //如果有左儿子，并且左儿子小，让左儿子上移
    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)//如果当前根节点不是最小的那个数，就交换
    {
        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]);

    cnt=n;
    for(int i=n/2;i;i--)down(i);//这是n/2，叶子节点占1/2n，将小数不断上移，构成小根堆

    while(m--)
    {

        printf("%d ",h[1]);//h[1]就是堆排序中最小的数
        h[1]=h[cnt];//cnt是最后一个节点，让最后一个点覆盖掉第一个点
        cnt--;//覆盖掉之后，节点数减减

        down(1);
    }


    return 0;
}