题解：P3378 【模板】堆

前置知识

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

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

$\operatorname{O}(\log_2n)$ 插入一个元素（ $n$ 是已有元素的数量）；
将放进来的元素自动排序。

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

CPP

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 应用到本题中。

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

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

后言

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

代码

CPP

#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();
    }
}

题解：P3378 【模板】堆

文章操作

前置知识

特殊注意

STL 应用

后言

代码

相关推荐

评论

题解：P3378 【模板】堆