一、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 . . .
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 . . .
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 . . .
