题解：P3378 【模板】堆

Doraeman · 2025-08-25 22:51:57 · 题解

前置知识

这道题需要介绍一个强大的 STL：priority_queue。

它主要可以实现的功能是：

• 将放进来的元素自动排序。

与队列用法相似，以下是主要用法：

q.top()   //得到堆顶元素，并不会弹出
q.pop()   //删除堆顶元素
q.push(x)  //往堆里面插入元素x
q.empty() //查询堆是否为空, 为空则返回1, 否则返回0
q.size()  //查询堆内元素数量

特殊注意

priority_queue 默认从大到小排序，如果要从小到大排序则需多加一点东西。

• 定义“大根堆”（从大到小排序）：
  priority_queue <int> q;
• 定义“小根堆”（从小到大排序）：
  priority_queue <int, vector<int>, greater<int>> q;

STL 应用

现在把这个 STL 应用到本题中。

1. q.push(x); 实现操作 1；
2. cout << q.top() << '\n'; 实现操作 2；
3. q.pop(); 实现操作 3。

就这么结束了？
当然没有。

后言

那么，这道题和二叉树以及算法标签上写的“堆”有什么关系呢？
其实 priority_queue 是一种 STL 自带的堆实现。但是也可以手写堆（你好原始人）。
具体应该怎么写呢？其实我也不知道——但是现在我知道了。
这篇文章 通过画图解释了堆的实现过程以及堆与二叉树的关系，解释得非常清晰，可以去看看。

代码

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

priority_queue <int, vector<int>, greater<int>> a;

int main(){
    int Q; cin >> Q;
    while(Q--){
        int op; cin >> op;
        if(op == 1){
            int x; cin >> x;
            a.push(x);
        }
        else if(op == 2)
            cout << a.top() << '\n';
        else a.pop();
    }
}