c++ 优先队列(priority_queue)priority_queue大顶堆与小顶堆

69 阅读 0 评论 46 点赞

我是靠谱客的博主细腻心锁，这篇文章主要介绍c++ 优先队列(priority_queue)priority_queue大顶堆与小顶堆，现在分享给大家，希望可以做个参考。

优先队列的本质是堆，但它具有队列的所有操作特性，与普通队列不同的地方就是出队的时候按照优先级顺序出队，这个优先级即最大堆或最小堆的规则（即大的为top优先出队或小的为top优先出队），在队列的基础上加了个堆排序。

以O(log n) 的效率查找一个队列中的最大值或者最小值，其中是最大值还是最小值是根据创建的优先队列的性质来决定的。

priority_queue

对于这个模板类priority_queue，它是STL所提供的一个非常有效的容器。

作为队列的一个延伸，优先队列包含在头文件 <queue> 中

C ++中的优先队列是STL中的派生容器，它仅考虑最高优先级元素。队列遵循FIFO策略，而优先队列根据优先级弹出元素，即，优先级最高的元素首先弹出。

它在某些方面类似于普通队列，但在以下方面有所不同：

在优先队列中，队列中的每个元素都与某个优先级相关联，但是优先级在队列数据结构中不存在。

优先队列中具有最高优先级的元素将被首先删除，而队列遵循FIFO（先进先出）策略，这意味着先插入的元素将被首先删除。

如果存在多个具有相同优先级的元素，则将考虑该元素在队列中的顺序。

注意：优先队列是普通队列的扩展版本，但优先级最高的元素将首先从优先队列中删除。

优先队列的语法

priority_queue<Type, Container, Functional>

其中Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。

1.在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

2.用到最小堆，则一般要把模板的三个参数都带进去。

STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明最小堆(升序)

大顶堆与小顶堆

大顶堆（降序）

//构造一个空的优先队列（此优先队列默认为大顶堆）
priority_queue<int> big_heap;

//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;

小顶堆（升序）

//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;

注意事项
需要注意的是，如果使用less和greater，需要头文件：

#include <functional>

我们通过使用push()函数插入元素，并且插入操作与普通队列相同。但是，当我们使用pop()函数从队列中删除元素时，优先级最高的元素将首先被删除。

优先队列的成员函数

函数	描述
push()	它将新元素插入优先队列。
pop()	它将优先级最高的元素从队列中删除。
top()	此函数用于寻址优先队列的最顶层元素。
size()	返回优先队列的大小。
empty()	它验证队列是否为空。基于验证，它返回队列的状态。
swap()	它将优先队列的元素与具有相同类型和大小的另一个队列交换。
emplace()	它在优先队列的顶部插入一个新元素。

具体用法：

假设type类型为int，则：

bool empty() const 返回值为true，说明队列为空；
int size() const 返回优先队列中元素的数量；
void pop() 删除队列顶部的元素，也即根节点
int top() 返回队列中的顶部元素，但不删除该元素；
void push(int arg) 将元素arg插入到队列之中；

让我们创建一个简单的优先队列程序。

示例

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include<queue>
using namespace std;
int main()
{
 priority_queue<int> p;  // 变量声明.
 p.push(10); // 插入 10 到队列, top=10
 p.push(30); // 插入 30 到队列, top=30
 p.push(20); // 插入 20 到队列, top=20
 cout<<"可用元素的数量 到 'p' :"<<p.size()<<endl;
 while(!p.empty())
 {
     cout << p.top() <<endl; 
     p.pop();
 }
 return 0;
}

注意其中的priority_queue<int> p; // 变量声明，<>中只有第一个参数，所以是最大堆优先级

在上面的代码中，我们创建了一个优先队列，在其中插入三个元素，即10、30、20。在插入这些元素之后，我们使用while循环显示优先队列的所有元素。

输出结果

复制代码

1
2
3
4
可用元素的数量 到 'p' :3
30
20
10

让我们看看优先队列的另一个示例。

示例

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include<queue>
using namespace std;
int main()
{
   priority_queue<int> p;  //优先队列声明
   priority_queue<int> q;  //优先队列声明
   p.push(1); // 插入 '1' 到 p.
   p.push(2); // 插入 '2' 到 p.
   p.push(3); // 插入 '3' 到 p.
   p.push(4); // 插入 '4' 到 p.
   q.push(5); // 插入 '5' 到 q.
   q.push(6); // 插入 '6' 到 q.
   q.push(7); // 插入 '7' 到 q.
   q.push(8); // 插入 '8' 到 q.
   p.swap(q);
   cout << "p队列元素是 : " <<endl;
   while(!p.empty())
   {
      cout << p.top() <<endl;
       p.pop();
   }
   cout << "q优先队列元素是 :" <<endl;
    while(!q.empty())
   {
     cout << q.top() <<endl;
       q.pop();
   }
    return 0;
}

在上面的代码中，我们声明了两个优先队列，即p和q。我们在“ p”优先队列中插入了四个元素，在“ q”优先队列中插入了四个元素。插入元素之后，我们使用swap()函数将'p'队列的元素与'q'队列交换。

输出结果

复制代码

复制代码如果要按照最小堆优先级
```
1
如果要按照最小堆优先级
```

priority_queue<Type, Container, Functional>

写入程序中就是priority_queue<int, vector<int>, greater<int> > q;

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h> 
using namespace std;
int main(){
    priority_queue<int, vector<int>, greater<int> > q;
    for( int i= 0; i< 10; ++i ) 
    {
		int temp;
		cin>>temp; 
		q.push(temp);
	}
    while( !q.empty() ){
        cout << q.top() << endl;
        q.pop();
    }     
    getchar();
    return 0;
}