洛谷 P3378 【模板】堆

嗯...

 

这是一道堆的模板题，但我个人感觉最好的做法就是通过优先队列来进行操作...

 

首先我们看一下这道水题....

 

题目描述

如题，初始小根堆为空，我们需要支持以下3种操作：

操作1： 1 x 表示将x插入到堆中

操作2： 2 输出该小根堆内的最小数

操作3： 3 删除该小根堆内的最小数

输入输出格式

输入格式：

 

第一行包含一个整数N，表示操作的个数

接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：

操作1： 1 x

操作2： 2

操作3： 3

 

输出格式：

 

包含若干行正整数，每行依次对应一个操作2的结果。

 

输入输出样例

输入样例#1： 
5 1 2 1 5 2 3 2 输出样例#1： 
2 5

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=15

对于70%的数据：N<=10000

对于100%的数据：N<=1000000（注意是6个0。。。不过不要害怕，经过编者实测，堆是可以AC的）

样例说明：

故输出为2、5

 

在这里只介绍关于优先队列的两种做法：

 

方法一：用优先队列默认的大根堆，并在输入输出时进行取反操作....（见代码１）

 

1 #include<cstdio>2 #include<iostream>3 #include<queue> // 优先队列的头文件与队列的头文件相同 4 5 using namespace std;6 7 // 默认优先队列中的top和pop操作都是对最大值进行操作 8 9 priority_queue <int> q; // 优先队列的定义 10 int main(){ 11 int n; 12 int a, b; 13 scanf("%d",&n); 14 for(int i = 1; i <= n; i++){ 15 scanf("%d", &a); //先将第一个数输入 16 //进行三种判断 17 if(a == 1){ 18 scanf("%d",&b); 19 q.push(-b); //入堆时进行取反操作，原来最大的变成了最小的，则就完成了一个小根堆的操作，只需在输出时进行又一次取反即可 20 } 21 if(a == 2){ 22 printf("%d\n",-q.top()); //出堆时又进行取反，其结果仍为原数 23 } 24 if(a == 3){ 25 q.pop(); //将堆中最大的数弹出，即为删除了最小元素 26 } 27 } 28 return 0; 29 } 30 View Code

 

方法二：用优先队列自己定义的小根堆，从小到大排序....（见代码２）

 

1 #include<cstdio>2 #include<iostream>3 #include<queue> // 优先队列的头文件与队列的头文件相同 4 5 using namespace std;6 7 // 自己更改后的优先队列中的top和pop操作都是对最小值进行操作 8 9 priority_queue <int,vector<int>,greater<int> > q; // 从小到大的优先队列的定义 10 int main(){ 11 int n; 12 int a, b; 13 scanf("%d",&n); 14 for(int i = 1; i <= n; i++){ 15 scanf("%d", &a); //先将第一个数输入 16 //进行三种判断 17 if(a == 1){ 18 scanf("%d",&b); 19 q.push(b); //无需进行取反，直接进堆 20 } 21 if(a == 2){ 22 printf("%d\n",q.top()); //直接输出即可 23 } 24 if(a == 3){ 25 q.pop(); //将堆中最小的数弹出，即为删除了最小元素 26 } 27 } 28 return 0; 29 } View Code

 

关于优先队列，其功能比队列强大很多，但速度很慢...

 

第一种方法比第二种方法要快一些，因为第一种只进行取反，而第二种又自己进行定义，所以第二种更慢...

 

转载于:https://www.cnblogs.com/New-ljx/p/10416241.html

总结

以上是生活随笔为你收集整理的洛谷 P3378 【模板】堆的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。