C++ 实现堆排序

• 思路：数组模拟小根堆
• 1、数组下标（堆顶）从1开始，若当前节点下标为u，则父节点下标为u/2，左儿子下标为u*2，右儿子下标为u*2+1
• 2、down(u)函数实现将下标为u的数放到小根堆的合理位置，down的前提是u的左右子树均为小根堆，因此需要从最后一个叶子节点的父节点(n/2)开始down
• 3、建堆操作：首先加入所有元素到数组中，然后从底层向根节点开始执行down操作调整所有元素至正确位置
• 4、插入操作：添加元素到数组末尾，然后从底层向根节点开始执行down操作调整所有元素至正确位置
• 5、弹出堆顶的操作：首先获取堆顶元素(h[1])，然后交换堆顶和堆的最后一个元素，堆大小减1，调整新元素到堆的正确位置
• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

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

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int h[N], cnt;

void down(int u) {
    int t = u; // t是当前节点的下标，u * 2是左儿子的下标，u * 2 + 1是右儿子的下标
    if (u * 2 <= cnt && h[t] > h[u * 2]) t = u * 2; // 不越界且大于左儿子就交换
    if (u * 2 + 1 <= cnt && h[t] > h[u * 2 + 1]) t = u * 2 + 1; // 不越界且大于右儿子就交换
    if (t != u) { // 如果需要交换，则继续down
        swap(h[u], h[t]);
        down(t);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) cin >> h[i];
    
    cnt = n;
    for (int i = n / 2; i; i--) down(i);  // 注意遍历到下标为1为止
    
    for (int i = 0; i < m; i++) {
        cout << h[1] << ' ';
        h[1] = h[cnt--];
        down(1);
    }
    cout << endl;
    
    return 0;
}