算法板子

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N], m, n, Size;
void down(int u) {
    int t = u;
    if (u * 2 <= Size && h[t] > h[u * 2]) t = u * 2;
    if (u * 2 + 1 <= Size && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
    if (t != u) {
        swap(h[t], h[u]);
        down(t);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    Size = n;
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    for (int i = n / 2; i; --i) down(i);
    while (m--) {
        cout << h[1] << " ";
        h[1] = h[Size--];
        down(1);
    }
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/heap-sort/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。