思路(字丑勿喷)

注：如果看完笔记还不太了解堆，可以看一下我之前的博客，里面有堆的实现、两种建堆方式(含时间复杂度分析)、堆排序和堆排，有兴趣可以看一下：

• 堆实现
• 堆排和topk(含建堆分析和时间复杂度分析)

代码

有注释

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int hp[N], sz, n, m;

// 向下调整
void down(int u)
{
    // 求父亲，左右孩子中最小的一个
    int t = u;
    // 若左孩子不超过 sz 并且左孩子小于父亲
    if (2 * u <= sz && hp[2 * u] < hp[t]) {
        t = 2 * u;
    }
    // 若右孩子不超过 sz 并且右孩子比现在最小的 t 更小
    if (2 * u + 1 <= sz && hp[2 * u + 1] < hp[t]) {
        t = 2 * u + 1;
    }
    // 如果 t 和 u 不等，则需要向下调整
    if (t != u) {
        swap(hp[t], hp[u]);
        // 当前 t 为刚刚调整下来的位置，继续检查 t 是否需要调整
        // 递归处理
        down(t);
    }
}

// 向上调整
int up(int u)
{
    // 父亲不为假并且父亲大于儿子
    // 就把父亲拉下来，并让儿子篡位
    while (u / 2 && hp[u / 2] > hp[u]) {
        swap(hp[u / 2], hp[u]);
        u /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    // 从 1 位置开始
    for (int i = 1; i <= n; i++) {
        cin >> hp[i];
    }
    sz = n;

    // 向下调整建堆
    for (int i = n / 2; i; i--) {
        down(i);
    }

    // 每次打印堆顶并删除
    // 之后交换堆顶和堆底元素，并让 sz -- ，向下调整
    for (int i = 1; i <= m; i++) {
        cout << hp[1] << ' ';
        swap(hp[1], hp[sz--]);
        down(1);
    }

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int hp[N], sz, n, m;

void down(int u)
{
    int t = u;
    if (2 * u <= sz && hp[2 * u] < hp[t]) {
        t = 2 * u;
    }
    if (2 * u + 1 <= sz && hp[2 * u + 1] < hp[t]) {
        t = 2 * u + 1;
    }
    if (t != u) {
        swap(hp[t], hp[u]);
        down(t);
    }
}

int up(int u)
{
    while (u / 2 && hp[u / 2] > hp[u]) {
        swap(hp[u / 2], hp[u]);
        u /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

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

    for (int i = n / 2; i; i--) {
        down(i);
    }

    for (int i = 1; i <= m; i++) {
        cout << hp[1] << ' ';
        swap(hp[1], hp[sz--]);
        down(1);
    }

    return 0;
}