题解：P3378 【模板】堆

Xing_Yang · 2025-05-04 10:05:42 · 题解

堆这个结构我也不会是一种特殊的二叉树，由于我是个偷懒小孩习惯从简原则，所以不想手写怎么实现插入，删除中保持堆的代码用了STL，大家可以参阅下。 应该没人会用大根堆来实现小根堆吧

#include<iostream>
#include<cstdio>
#include<queue>
#include<ctime>
using namespace std;
priority_queue<int> queque;                         //大根堆（其实大根堆也可以实现小根堆的效果，就是略微麻烦一点）
//priority_queue<int,vector<int>,greater<>> quequex;//小根堆
                                                    //greater<> <>里可以不写，类型默认在vector的<>里
int main() {
#if defined(_DEBUG) && _DEBUG==1
    freopen("read6.txt", "r", stdin);
    freopen("write6.txt", "w", stdout);
#endif
    int n,s;
    cin>>n;
    while(n--){
        cin>>s;
        switch (s) {
        case 1:
            cin>>s;
            queque.emplace(-s);//s前加个负号，这个堆就变成了小根堆（自己实验）
//          quequex.emplace(s);//小根堆前不用加，加了的效果：小根堆变成大根堆
            break;
        case 2:
            cout<<-queque.top()<<endl;//在加入时是负数，所以加个负号
                                      //或abs()。
                                      //小根堆不用
            break;
        case 3:
            queque.pop();//正常删除，pop自带的
            break;
        }
    }
#if defined(_DEBUG) && _DEBUG==1
    printf("\nTime used=%ldms", clock());
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;
}
/*你问我
#if defined(_DEBUG) && _DEBUG==1
    freopen("read6.txt", "r", stdin);
    freopen("write6.txt", "w", stdout);
#endif
干嘛用？别说，
#if defined(_DEBUG) && _DEBUG==1
    printf("\nTime used=%ldms", clock());
    fclose(stdin);
    fclose(stdout);
#endif
这个也是测试用的（提交的话以上内容无效）
*/