题目描述

堆排序

自己构造堆,不用STL

小根堆：即根节点是最小的

时间复杂度

构建堆的过程时间复杂度为O(n);查找的时间复杂度为O(1)

C++ 代码

#include<iostream>
using namespace std;
const int N=100010;
int h[N],sizee;
int n,m;
void down(int u)
{
    int t=u;
    if(2*u<=sizee&&h[2*u]<h[t])t=2*u;            //根节点和左节点比较
    if(2*u+1<=sizee&&h[2*u+1]<h[t])t=2*u+1;      //根节点和右节点比较

    //若此时较小的节点不是根节点
    if(t!=u)
    {
        swap(h[u],h[t]);        //就交换两个节点的位置，将较小的换到根节点的位置
        down(t);
    }
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>h[i];
    sizee=n;                        //节点数量
    for(int i=n/2;i;i--)           //因为题中只需输出前几个小数，所以截半
    {
        down(i);        //由底向上查找
    }
    while(m--)
    {
        cout<<h[1]<<" ";       //每次输出根节点
        h[1]=h[sizee];        //取代已经输出的数
        sizee--;
        down(1);         //将次小的数换到根节点的位置
    }
    return 0;
}