priority_queue的相关介绍
- 优先级队列是一种容器适配器,根据严格的排序标准,它的第一个元素总是它所包含的元素中最大(小)的。
- 该容器适配器类似于堆,在堆中可以随时插入元素,并且可以检索最大(小)堆元素(优先级队列中位于顶部的元素)。
- 优先级队列被实现为容器适配器,容器适配器即 将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先级队列的顶部。
- 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应可以通过随机访问迭代器访问。
- 标准容器类vector和deque皆满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
更多关于priority_queue的详细内容,请点击priority_queue的文档介绍
priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。
函数声明 | 接口说明 |
priority_queue() priority_queue(InputIterator first, InputIterator last) | 无参构造 迭代器区间初始化构造 |
empty() | 检查优先级队列是否为空 |
top() | 返回优先级队列中最大(最小元素),即堆顶元素 |
push(x) | 在优先级队列中插入元素x |
pop() | 删除优先级队列中最大(最小)元素,即堆顶元素 |
// 使用举例(和queue类似)
int arr[] = { 3,2,7,6,0,4,1,9,8,5 };
// 迭代器区间初始化
priority_queue<int> pq1(arr, arr + sizeof(arr) / sizeof(arr[0]));
while (!pq1.empty()) // 判断优先级队列是否为空
{
cout << pq1.top() << " "; // 获取栈顶元素
pq1.pop(); // 删除元素
}
cout << endl;
// 结果为:9,8,7,6,5,4,3,2,1,0
上述代码结果默认是大堆(降序),其默认仿函数为less(),若想得到升序序列,只需改变仿函数为greater()即可。
// 改变仿函数
priority_queue<int, vector<int>, greater<int>> pq1(arr, arr + sizeof(arr) / sizeof(int));
priority_queue的底层实现
ps. 默认情况下,创建的是大堆,其底层按照小于号比较
// 迭代器区间初始化
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
//建堆
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i); //向下调整算法
}
}
// 向上调整算法
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
// 使用仿函数
if (_comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// 插入
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
// 向下调整算法
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
// 使用仿函数
if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
{
++child;
}
if (_comFunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//删除
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}