题目描述

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式
第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围
1≤m≤n≤105，
1≤数列中元素≤109

样例

输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

算法1

建堆时间复杂度 logn
1 建堆 从 n / 2 出开始，使得时间为logn
2 输出前m个元素， 交换1 与 size元素， down(1)一遍
3 down操作：比较当前节点与两个子节点的大小，找到最小的值，与当前结点交换，之后递归操作每个节点

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int s;

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

int main(){
    int n, m;
    cin>>n>>m;
    s = n;
    vector<int> h(n + 1, 0);

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

    for(int i = s / 2; i; --i) down(h, i);

    for(int i = 1; i <= m; ++i){
        cout<<h[1]<<' ';
        h[1] = h[s];
        --s;
        down(h, 1);
    }
    return 0;
}