题目描述

模板题：堆
这个堆的实现方法真不错~

C++代码

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

const int N = 1e5 + 10;
int n, m;
int h[N], s;
// 小根堆~

void down(int u){
    int t = u;
    if(2*u <= s && h[2*u] < h[t]) 
        t = u * 2;
    if(2*u + 1 <= s && h[2*u+1] < h[t])
        t = u * 2 + 1;
    // 相当于父、左孩子、右孩子 三个数中选小的，所以使用上面三步
    if(t != u){
        swap(h[u], h[t]);
        down(t);
    }
}
//这个up这里用不上，但是插入堆时用得着~
void up(int u){
    while(u / 2 && h[u / 2] > h[u]){
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}

int main(){
    cin >> n >> m;
    for(int i =1; i <= n; i++) //之所以数组从1开始，因为从0的话左孩子 2*0 = 0 还得单独处理
        scanf("%d", &h[i]);
    s = n;
    for(int i = n / 2; i; i--) //这种写法可以使得建堆复杂度为O(n)
        down(i);
    while(m--){
        cout << h[1] << " ";
        h[1] = h[s];
        s--;
        down(1);
    }
    return 0;
}