[数据结构与算法]ACWING 838. 堆排序

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

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

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

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

数据范围
1≤m≤n≤105，
1≤数列中元素≤109
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

https://www.acwing.com/problem/content/840/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 100010;

int a[N];
int n, m;

void up(int k) {
    int t;

    while (k > 0 && a[k >> 1] > a[k]) {
        t = a[k >> 1];
        a[k >> 1] = a[k];
        a[k] = t;

        k >>= 1;
    }
}

void down(int k) {
    int t;

    while (k * 2 + 1 <= n && (a[k] > a[k * 2] || a[k] > a[k * 2 + 1])) {
        if (a[k * 2] < a[k * 2 + 1]) {
            t = a[k * 2];
            a[k * 2] = a[k];
            a[k] = t;

            k <<= 1;

        } else {
            t = a[k * 2 + 1];
            a[k * 2 + 1] = a[k];
            a[k] = t;

            k = (k << 1) + 1;
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        up(i);
    }

    for (int i = 1; i <= m; i++) {
        cout << a[1] << " ";
        a[1] = a[n--];
        down(1);
    }
    cout << "\n";

    return 0;
}