priority_queue的使用
priority_queue文档介绍
priority_queue简介
- 优先队列是一种容器适配器，有严格的排序标准，它的第一个元素总是它所包含的元素中最大的(或最小的)。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆(或 最小堆)元素(优先队列中位于顶部的元素)。
- 默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
priority_queue的使用
| 成员函数 | 功能 |
|---|---|
| push | 插入数据 |
| pop | 删除优先级队列中最大(最小)元素，即堆顶元素 |
| top | 返回优先级队列中最大(最小)元素，即堆顶元素 |
| empty | 检测优先级队列是否为空 |
| size | 获取队列中有效元素个数 |
void TestPriorityQueue()
{
// 默认情况下，创建的是大堆，其底层按照小于号比较
vector<int> v{ 3, 2, 7, 6, 0, 4, 1, 9, 8, 5 };
priority_queue<int> q1;// 构建优先级队列
for (auto e : v)
q1.push(e);//尾插
cout << "q1中元素个数:" << q1.size() << endl;
for (size_t i = 0;i<v.size();++i)
{
cout << q1.top() << " ";//输出栈顶的数据
q1.pop();//尾删
}
cout << endl;
cout << "q1中元素个数:" << q1.size() << endl;
cout << endl;
// 如果要创建小堆，将第三个模板参数换成greater比较方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
for (size_t i = 0; i<v.size(); ++i)
{
cout << q2.top() << " ";//输出栈顶的数据
q2.pop();//尾删
}
cout << endl;
}
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueue()
{
// 大堆，需要用户在自定义类型中提供<的重载
priority_queue<Date> q1;
q1.push(Date(2022, 1, 7));
q1.push(Date(2022, 1, 1));
q1.push(Date(2022, 1, 31));
cout << q1.top() << endl;
cout << endl;
// 如果要创建小堆，需要用户提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2022, 1, 7));
q2.push(Date(2022, 1, 1));
q2.push(Date(2022, 1, 31));
cout << q2.top() << endl;
}
priority_queue的模拟实现
priority_queue的底层实际上就是堆结构,可以参考博主之前写的有关堆的文章数据结构之堆
namespace nzb
{
//比较方式（使内部结构为大堆）
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
//比较方式（使内部结构为小堆）
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
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(size_t child)
{
size_t parent = (child - 1) / 2;//找到父节点
while (child > 0)
{
if (_com(_con[parent], _con[child]))//判断是否需要交换
{
//交换父子结点
swap(_con[parent], _con[child]);
//继续向上调整
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;//算出左子节点的下标
while (child < _con.size())
{
//找出子结点中符合比较方式的值
if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
{
child++;
}
//通过所给比较方式确定是否需要交换结点位置
if (_com(_con[parent], _con[child]))
{
//交换父子结点
swap(_con[parent], _con[child]);
//继续向下调整
parent = child ;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//插入数据
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);//将最后一个元素向上调整
}
//删除数据
void pop()
{
swap(_con[0], _con[_con.size() - 1]);//交换首尾数据
_con.pop_back();//尾删
AdjustDown(0);//首元素向下调整
}
//访问头元素
const T& top() const
{
return _con[0];
}
//获取队列中有效元素个数
size_t size()
{
return _con.size();
}
//判空
bool empty()
{
return _con.empty();
}
private:
Container _con;//底层容器
Compare _com;//比较方式
};
}
到此这篇关于C++中priority_queue的使用与模拟实现的文章就介绍到这了,更多相关C++ priority_queue内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
