时间复杂度

对于一个元素一个元素插入的O（nlongn）
从倒数第二层开始down为O（n）

C++ 代码

#include<iostream>
using namespace std;
const int N=100005;
int h[N];
int n,m,siz;
void down(int u){
    int t=u;
    if(u*2<=siz && h[u*2]<h[t]) t=u*2;
    if(u*2+1<=siz && h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t){
        swap(h[t],h[u]);
        down(t);
    }
}
int main(){
    cin>>n>>m;
    siz=n;
    for(int i=1;i<=n;i++) cin>>h[i];

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

    while(m--){
        cout<<h[1]<<" ";
        h[1]=h[siz];
        siz--;
        down(1);
    }
    return 0;
}