【C++】STL 容器 - priority_queue 优先级队列容器 ( 容器简介 | 容器操作性能分析 | 默认优先级队列容器 | 最大值优先级队列 | 最小值优先级队列 )

怼烎@ 2024-02-05 19:05 53阅读 0赞

#### 文章目录 ####

*  一、priority\_queue 优先级队列容器
 *   *  1、priority\_queue 优先级队列容器简介
     *  2、priority\_queue 优先级队列容器操作性能分析
 *  二、代码示例 - priority\_queue 优先级队列容器
 *   *  1、默认优先级队列容器
     *  2、最大值优先级队列
     *  3、最小值优先级队列

## 一、priority\_queue 优先级队列容器 ##

--------------------

### 1、priority\_queue 优先级队列容器简介 ###

**容器简介 :** priority\_queue 优先级队列容器 是一种数据结构 , 可以 存储元素并根据优先级进行访问 ;

**容器元素顺序排列 :** priority\_queue 优先级队列容器 中的 元素顺序 , 是根据 优先级 决定的 , 优先级 最高的元素 , 位于 队列的 顶部 / 首部 / 队头 位置 ;

**容器元素自动排序 :** priority\_queue 优先级队列容器 会对元素 进行自动排序 , 确保 优先级最高的 元素 , 在队首位置 ;

**优先级比较函数 :** 对 元素 进行优先级排序 需要一个 比较函数 , 系统根据元素类型 默认指定了一个比较函数 ; 开发者也可以根据自己的需求 , 自定义比较函数 ;

**底层容器选择 :** priority\_queue 优先级队列容器 可以 与任何满足特定需求的底层容器结合使用 , 如 : vector 动态数组容器 , deque 双端数组容器 , list 双向链表容器 ;

**导入的头文件 :** 使用 priority\_queue 优先级队列容器 之前 , 需要 导入 <queue> 头文件 ;

#include <queue>

### 2、priority\_queue 优先级队列容器操作性能分析 ###

**priority\_queue 优先级队列容器操作性能分析 :**

*  **调用 top 函数访问顶部元素 :** 时间复杂度是 O(1) , 无论 容器中有多少元素 , 访问顶部元素只需要直接取出访问即可 ;
 *  **调用 pop 函数删除顶部元素 :** 时间复杂度是 O(1) , 直接将 顶部元素 删除即可 , 下一个元素自动称为新的顶部元素 ;
 *  **调用 empty 函数判断容器是否为空 :** 时间复杂度是 O(1) , 与 访问顶部元素 时间复杂度是一样的 , 只需要查看是否存在顶部元素即可 , 存在则不为空 , 不存在则为空 ;
 *  **调用 push 函数向容器中插入元素 :** 时间复杂度是 O(log n) , 插入元素时 , 一开始元素在队尾 , 需要进行上浮操作 , 将其放置在正确的位置 ; 容器默认的数据结构是堆 , 也就是 完全二叉树 , 其排序上浮的时间复杂度是 O(log n) ;

## 二、代码示例 - priority\_queue 优先级队列容器 ##

--------------------

### 1、默认优先级队列容器 ###

使用 如下代码 , 定义的 优先级队列容器 是 " 最大值优先级队列 " , 调用 top() 函数获取的队头首元素是最大值 ;

priority_queue<int> p;

优先级队列的 api 操作与 queue 类似 ;

*  调用 push 函数 , 可以向容器中加入元素 , 加入时会自动排序放到合适位置 ;
 *  调用 pop 函数 , 可以将 队头元素 移除队列 ;
 *  调用 top 函数 , 可以获取 首元素 ;
 *  调用 size 函数 , 可以获取 容器大小 ;

**代码示例 :**

#include "iostream"
    using namespace std;
    #include "queue"
    
    int main() {
        
    
    	// 默认优先级队列 
    	// 最大值优先级队列 首部元素是最大值
    	priority_queue<int> p;
    
    	// 向优先级队列容器中加入元素
    	p.push(3);
    	p.push(1);
    	p.push(5);
    	p.push(2);
    
    	// 获取队头元素
    	cout << "首元素 : " << p.top() << endl;
    
    	// 获取容器大小
    	cout << "容器大小 : " << p.size() << endl;
    
    	// 容器元素内容遍历
    	cout << "容器元素 : ";
    	while (p.size() > 0)
    	{
        
    		// 获取首元素
    		cout << p.top() << " ";
    		// 首元素出队
    		p.pop();
    	}
    	// 回车换行
    	cout << endl;
    
    
    	// 控制台暂停 , 按任意键继续向后执行
    	system("pause");
    
    	return 0;
    };

**执行结果 :**

首元素 : 5
    容器大小 : 4
    容器元素 : 5 3 2 1
    Press any key to continue . . .

![在这里插入图片描述][b24fa97bb112434fb26e2fa91e57aeae.png]

### 2、最大值优先级队列 ###

使用 如下代码 , 手动定义 " 最大值优先级队列 " , 下面的队列效果与 `priority_queue<int> p` 是一样的 ;

priority_queue<int , vector<int>, less<int>> p;

**代码示例 :**

#include "iostream"
    using namespace std;
    #include "queue"
    
    int main() {
        
    
    	// 最大值优先级队列 
    	// 最大值优先级队列 首部元素是最大值
    	priority_queue<int, vector<int>, less<int>> p;
    
    	// 向优先级队列容器中加入元素
    	p.push(3);
    	p.push(1);
    	p.push(5);
    	p.push(2);
    
    	// 获取队头元素
    	cout << "首元素 : " << p.top() << endl;
    
    	// 获取容器大小
    	cout << "容器大小 : " << p.size() << endl;
    
    	// 容器元素内容遍历
    	cout << "容器元素 : ";
    	while (p.size() > 0)
    	{
        
    		// 获取首元素
    		cout << p.top() << " ";
    		// 首元素出队
    		p.pop();
    	}
    	// 回车换行
    	cout << endl;
    
    
    	// 控制台暂停 , 按任意键继续向后执行
    	system("pause");
    
    	return 0;
    };

**执行结果 :**

首元素 : 5
    容器大小 : 4
    容器元素 : 5 3 2 1
    Press any key to continue . . .

![在这里插入图片描述][b0285d24f85d434e9beaa4e9845cd979.png]

### 3、最小值优先级队列 ###

使用 如下代码 , 手动定义 " 最小值优先级队列 " , 下面的队列效果与 `priority_queue<int> p` 是一样的 ;

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

**代码示例 :**

#include "iostream"
    using namespace std;
    #include "queue"
    
    int main() {
        
    
    	// 最小值优先级队列 
    	// 最小值优先级队列 首部元素是最小值
    	priority_queue<int, vector<int>, greater<int>> p;
    
    	// 向优先级队列容器中加入元素
    	p.push(3);
    	p.push(1);
    	p.push(5);
    	p.push(2);
    
    	// 获取队头元素
    	cout << "首元素 : " << p.top() << endl;
    
    	// 获取容器大小
    	cout << "容器大小 : " << p.size() << endl;
    
    	// 容器元素内容遍历
    	cout << "容器元素 : ";
    	while (p.size() > 0)
    	{
        
    		// 获取首元素
    		cout << p.top() << " ";
    		// 首元素出队
    		p.pop();
    	}
    	// 回车换行
    	cout << endl;
    
    
    	// 控制台暂停 , 按任意键继续向后执行
    	system("pause");
    
    	return 0;
    };

**执行结果 :**

首元素 : 1
    容器大小 : 4
    容器元素 : 1 2 3 5
    Press any key to continue . . .

![在这里插入图片描述][eaee94f83bc2491c835e3a688583bf90.png]

[b24fa97bb112434fb26e2fa91e57aeae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/6a96192bb3044edd9f8aed5b802f5919.png
[b0285d24f85d434e9beaa4e9845cd979.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/71c1e2b881aa413e91745ec990618277.png
[eaee94f83bc2491c835e3a688583bf90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/4c5e60a2565b4270af067e1a889852ab.png