838. 堆排序 - AcWing题库

问题分析

思路分析

执行流程设计

建堆

从第一个非叶子节点开始建堆，执行 down 函数。

弹出

将最后一个元素的值和根节点交换，然后删除最后一个元素。

总结

代码实现

下面是小根堆的实现。

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

const int N = 1e5 + 10;
int n, m, sz;
int a[N];

// 将根节点为 u 的完全二叉树堆化
void down(int u) {
    int t = u;
    // 把最大的孩子节点与根节点交换, 如果根节点比孩子小
    if (u * 2 <= sz && a[2 * u] < a[t]) t = 2 * u; // 大根堆只需要改 < 为 >
    if (u * 2 + 1 <= sz && a[2 * u + 1] < a[t]) t = 2 * u + 1; // 大根堆只需要改 < 为 >
    
    if (u != t) {
        swap(a[u], a[t]);
        down(t);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    sz = n;
    for (int i = n / 2; i; i--) {
        down(i);
    }
    
    while (m--) {
        cout << a[1] << " ";
        
        swap(a[1], a[sz]);
        
        sz--;
        
        down(1);
    }
    return 0;
}