堆——acwing

题目一：推排序

838. 堆排序 - AcWing题库

分析

代码 

优先队列，sort 也能解。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int h[N], idx;

int n, m;

void down(int u) {
    int t = u;
    // 根、左孩子、右孩子中最小值,然后和根交换值
    if(2*u<=idx && h[t] > h[u*2]) t = 2*u;
    if(2*u+1<=idx && h[t] > h[u*2+1]) t = u*2+1;
    if(u != t) {
        swap(h[u],h[t]);
        down(t);
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> h[i];
    idx = n;
    // 建堆
    for(int i = n/2; i > 0; i --) down(i);
    
    while(m --) {
        cout << h[1] << " ";
        h[1] = h[idx--];
        down(1);
    }
    return 0;
}

题目二、模拟堆

839. 模拟堆 - AcWing题库

分析

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int h[N], idx;
int hp[N], ph[N], num;

// a b 是完全二叉树中对应位置
void heap_swap(int a, int b) {
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);
}
// 向下，两分枝最小值交换，大则向下/三者比较
void down(int u) {
    int t = u;
    if(2*u <= idx && h[t] > h[2*u]) t = 2*u;
    if(2*u+1 <= idx && h[t] > h[2*u+1]) t = 2*u+1;
    if(u!=t) {
        heap_swap(t,u);
        down(t);
    }
}
// 小则向上，两比较
void up(int u) {
    while(u/2>0 && h[u/2] > h[u]) {
        heap_swap(u/2,u);
        u /= 2; 
    }
}

int main() {
    int _;
    cin >> _;
    
    while(_ --) {
        int k, x;
        char op[3];
        cin >> op;
        //用string也可以，用 char* 的比较函数也行strcmp
        // 插入x
        if(!strcmp(op,"I")) {
            cin >> x;
            idx ++, num ++;
            ph[num] = idx, hp[idx] = num;
            h[idx] = x;
            up(idx);
        }
        //输出min (堆顶)
        else if(!strcmp(op,"PM")) cout << h[1] << endl;
        //删除min
        else if(!strcmp(op,"DM")) {
            heap_swap(1,idx);
            idx --;
            down(1);
        }
        // 删除第k个插入的值
        else if(!strcmp(op,"D")) {
            cin >> k;
            k = ph[k];
            heap_swap(k,idx);
            idx --;
            down(k); up(k);
        }
        // 修改第k个插入的值为x
        else if(!strcmp(op,"C")) {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}