C++：优先队列-Priority_queue
目录
1.关于优先队列
在C++中，可以使用STL（标准模板库）中的priority_queue类来实现优先队列。priority_queue是一个模板类，可以存储任意类型的元素，并按照元素的优先级进行排序。
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2.类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
素 ) 。3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类， queue 提供一组特 定的成员函数来访问其元素。元素从特定容器的 “ 尾部 ” 弹出，其称为优先队列的顶部。4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问，并支持以下操作：empty() ：检测容器是否为空size() ：返回容器中有效元素个数front() ：返回容器中第一个元素的引用push_back() ：在容器尾部插入元素pop_back() ：删除容器尾部元素5.标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用vector 。6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap 、 push_heap 和 pop_heap 来自动完成此操作。
2.priority_queue的使用
如果要小堆，将第三个模板参数换成greater比较方式
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
int main()
{
vector<int>nums = { 1,2,4,6,78,4,23,65,3,12,5,45 };
priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.end());
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
return 0;
} 
1.构造方法
1.priority queue();
构造一个空的优先级队列
comp用于对堆进行排序的比较对象。这可能是一个函数指针或函数对象，能够通过比较其两个参数来执行严格的弱排序。
Compare 是第三类模板参数（默认为：less<T>）。默认为大根堆。
ctnr容器对象。
容器是第二个类模板参数（priority_queue的基础容器的类型;默认为：vector<T>）。
2.priority queue（first，last);
将迭代器输入到序列中的初始和最终位置。在对基础容器进行排序之前，将此序列中的元素插入到基础容器中。
使用的范围是 [first，last），它包括 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
2.empty();判空
返回priority_queue是否为空：即其大小是否为零。
此成员函数有效地调用基础容器对象的空成员。
3.size();
返回priority_queue中的元素数。
此成员函数有效地调用基础容器对象的成员大小。
4.top();
返回对 priority_queue 中顶部元素的常量引用。
top 元素是priority_queue中比较较高的元素，以及调用 priority_queue：:p op 时从容器中删除的下一个元素。此成员函数有效地调用基础容器对象的成员前端。
5.push(val);
在priority_queue中插入一个新元素。此新元素的内容初始化为 val。
此成员函数有效地调用基础容器对象的成员函数push_back，然后通过对包含容器的所有元素的范围调用 push_heap 算法，将其重新排序到堆中的位置。
6.pop();
移除priority_queue顶部的元素，有效地将其尺寸减小 1。删除的元素是具有最高值的元素。
在弹出之前，可以通过调用成员 priority_queue：：top 来检索此元素的值。此成员函数有效地调用 pop_heap 算法来保留 priority_queues 的堆属性，然后调用基础容器对象的成员函数pop_back来删除元素。这将调用已删除元素的析构函数。
3.优先队列模拟实现
在vector容器基础上利用堆的向上调整算法和向下调整算法来实现。插入删除时保持堆属性。
#pragma once
namespace wjc
{
template<class T>
struct less
{
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
template<class T,class Container=vector<T>,class Compare=less<T>>
class priority_queue
{
public:
priority_queue()
:_con()
{
};
template<class Iterator>
priority_queue(Iterator first, Iterator last)
:_con(first, last)
{
int count = _con.size();
int root = ((count - 1 - 1) / 2);
while (root >= 0)
{
AdjustDown(root);
root--;
}
}
void push(const T& data)
{
_con.pushback(data);
AdjustUp(_con.size() - 1);
}
void pop()
{
if (empty())
return;
swap(_con.front(), _con.back());
_con.pop_back();
AdjustDown(0);
}
bool empty()
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
const T& top()const
{
return _con.front();
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))
child++;
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child >= 0)
{
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
Container _con;
};
}测试代码
//如果需要升序排序 利用不同比较方法建小堆
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
#include"priority_queue.h"
int main()
{
vector<int> v = { 2,3,6,3,2,45,74,23,21 };
//wjc::priority_queue<int> p(v.begin(), v.end()); //默认大堆
//如果需要升序排序 利用不同比较方法建小堆
wjc::priority_queue<int,vector<int>,greater<int>> p(v.begin(), v.end());
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
return 0;
}
4.用优先队列解决数组中第K个大的元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> p(nums.begin(),nums.end());
while(--k)
{
p.pop();
}
return p.top();
}
};因为优先队列默认是大堆，所以删除--k个元素，堆顶就是第K大个元素，也就是p.top();
原文地址：https://blog.csdn.net/decade777555/article/details/135796159
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！