题解 | 【模板】堆

// // 活动地址： 牛客春招刷题训练营 - 编程打卡活动
// #include<iostream>
// #include<algorithm>
// #include<cmath>
// #include<vector>
// #include<stack>
// #define int long long 

// using namespace std;



// void solve(){
//      int  n;
//      cin>>n;
//      stack<int>s;
//      while(n--){
//         string t;
//         cin>>t;
//         if(t=="push"){ // 如果是push  
//             int x;
//             cin>>x;
//             s.push(x);
//         }
//         else if(t=="top"){
//             if(s.empty())cout<<"empty"<<"\n";
//             else cout<<s.top()<<"\n";
//         }
//         else {
//             if(s.empty())cout<<"empty"<<"\n";
//             else {
//                 cout<<s.top()<<"\n";
//                  s.pop();
               
               
//             }
//         }
//      }  
// }

// signed main(){
//     int T=1;
//     ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//     //cin>>T; // T 组数据
//     while(T--){
//         solve();
//     }
//     return 0;
// }
// 活动地址： 牛客春招刷题训练营 - 编程打卡活动

#include<bits/stdc++.h>
#include <vector>
using namespace std;
 /// 注意题目 说的是 实现一个 大根堆 所以 得用二叉树 来实现 
 /// 所以感觉这题还是有点超标的！
void down(int r, vector<int>& h, int size) {
    //h->heap;r->root;l->larger_one;
    int l = r;
    if (r * 2 <= size && h[r * 2] > h[l]) l = r * 2;
    if (r * 2 + 1 <= size && h[r * 2 + 1] > h[l]) l = r * 2 + 1;
    if (r != l) {
        swap(h[r], h[l]);
        down(l, h, size);
    }
    return;
}
void up(int c, vector<int>& h) {
    //h->heap;c->child;l->larger_one;
    int l = c;
    if (c % 2 == 0 && h[c / 2] < h[l]) l = c / 2;
    else if (c % 2 == 1 && h[(c - 1) / 2] < h[l]) l = (c - 1) / 2;
    if (c != l) {
        swap(h[c], h[l]);
        if (l > 1) up(l, h);
    }
    return;
}
int main() {
    int n = 0, size = 0, x = 0;
    string s;
    cin >> n;
    vector<int> heap(n + 1, 0);
    while (n--) {
        cin >> s;
        if (s == "push") {
            cin >> x;
            heap[++size] = x;
            if (size != 1) up(size, heap);
        } else if (s == "top") {
            if (heap[1]) {
                cout << heap[1] << endl;
            } else {
                cout << "empty" << endl;
            }
        } else {
            if (heap[1]) {
                cout << heap[1] << endl;
                swap(heap[1], heap[size]);
                heap[size--] = 0;
                down(1, heap, size);
            } else {
                cout << "empty" << endl;
            }
        }
    }
}