优先队列（stl）-白红宇

优先队列（stl）

阅读量：5087 次

发布时间：2019-06-13

本文共 1207 字，大约阅读时间需要 4 分钟。

优先队列是堆排的一种优化，我学习的是使用stl库的堆排。

基本操作有：

1.push将一个元素入队。

2.pop将一个元素出队。

3.top返还值为队头元素。

4.empty判断队列是否为空，为空返回真。

5.size返还队列里元素总数。

堆的定义方法有很多，我介绍一下我的定义方法

小根堆：priority_queue< int , vector<int> , greater<int> > q;

大根堆: priority_queue< int , vector<int> , greater<int> > q;

注意要用空格隔开后边的，不然会被系统判定为位运算.

以洛谷3378为例：http://www.luogu.org/problem/show?pid=3378

题目描述

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

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

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

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

输入输出格式

输入格式：

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

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

操作1： 1 x

操作2： 2

操作3： 3

输出格式：

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

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 priority_queue< int,vector
        
         ,greater
         
           > Q; 7 int N; 8  9 void init()10 {11     int x,y;12     cin>>N;13     for(int i=1;i<=N;i++){14         scanf("%d*c",&x);15         if(x==1){16             scanf("%d*c",&y);17             Q.push(y);18         }19         if(x==2){20             printf("%d\n",Q.top());21         }22         if(x==3){23             Q.pop();24         }25     }26 }27 28 int main()29 {30     init();31     return 0;32 }