堆排序 $O(nlogn)$

创建堆的时间复杂度是$O(n)$

#include <bits/stdc++.h>
using namespace std;

int n, m, a[100005];

void heap(int start, int end) {
    int dad = start, son = dad * 2 + 1;
    while (son <= end) {
        if (son + 1 <= end && a[son] < a[son + 1])
            son++;
        if (a[dad] > a[son])
            return;
        else {
            swap(a[dad], a[son]);
            dad = son, son = dad * 2 + 1;
        }
    }
}

void heapsort() {
    for (int i = n / 2; i >= 0; i--)
        heap(i, n - 1);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        heap(0, i - 1);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    heapsort();
    for (int i = 0; i < m; i++)
        cout << a[i] << ' ';
    cout << endl;
    return 0;
}