【C++】priority_queue&&priority_queue模拟实现

阅读本书更多章节>>>>

个人主页 ： zxctscl
如有转载请先通知

文章目录

1. priority_queue的介绍2. priority_queue的使用3. 函数模板与类模板4. 仿函数5. priority_queue模拟实现5.1 push5.2 pop5.3 empty5.4 size5.5 top5.6 仿函数实现大小堆5.7 实现自定义类型的优先级队列 6. 附模拟实现代码

1. priority_queue的介绍

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭
代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2. priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

来代码测试看看大堆：

void test_priority_queue(){priority_queue<int> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue();return 0;}

默认情况下，priority_queue是大堆

priority_queue默认情况下是less大堆，

想要priority_queue默认改为小堆，就得传三个参数。

用代码来测试一下:

#include<iostream>using namespace std;#include<vector>#include<queue>void test_priority_queue(){priority_queue<int,vector<int>,greater<int>> pq;pq.push(2);pq.push(1);pq.push(4);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}int main(){test_priority_queue();return 0;}

3. 函数模板与类模板

sort默认排序也是升序

  vector<int> v = { 3,1,7,4,6,3 };// 升序sort(v.begin(), v.end());for (auto e : v){cout << e << " ";}cout << endl;

想要将sort排序默认改为降序，就得加仿函数：

    vector<int> v = { 3,1,7,4,6,3 };sort(v.begin(), v.end(), greater<int>());for (auto e : v){cout << e << " ";}cout << endl;

sort这里是函数模板，函数参数传的是对象。

而priority_queue传的是类型，需要显示实例化

4. 仿函数

仿函数就是一个函数对象，就是一个类型。
先来实现一个类：

struct Less{bool operator()(const int& x, const int& y){return x < y;}};int main(){Less lessfunc;cout << lessfunc(1, 2) << endl;cout << lessfunc.operator()(1, 2) << endl;cout << Less()(1, 2) << endl;return 0;}

如果单独看红色框这一行，就会以为lessfunc是一个函数名，但它并不是，它是一个像函数的对象。

仿函数它的对象可以像函数一样去使用，本质上就是调用operator():
这两个是等价的：

还有能用匿名对象：

它本质上就是：

这里重载函数调用参数的()，其实就像[]一样，v[0]也就是v.operator：

本质上就是参数留下，变成运算符的操作数。
运算符重载中operator加运算符才是函数名，省略掉的就是.operator加括号。
一个类只要重载了operator()就可以调仿函数。

加模板就直接可以重载为泛型，什么类型就可以支持。

template<class T>struct Less{bool operator()(const T& x, const T& y){return x < y;}};int main(){Less<int> lessfunc;cout << lessfunc(1, 2) << endl;cout << lessfunc.operator()(1, 2) << endl;cout << Less<int>()(1, 2) << endl;cout << Less<int>().operator()(1, 2) << endl;return 0;}

这里定义类用struct和class有什么区别？
一般所有数据都公有就用struct，
有些公有，有些私有就用class。

5. priority_queue模拟实现

直接复用容器

5.1 push

插入一个数据后，向上调整，具体实现过程有需要可以看【数据结构】堆的实现

push代码：

void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0){if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}

5.2 pop

就这样删除效率太低了，通常首位交换一下。向下调整，具体实现过程有需要可以看【数据结构】堆的实现

pop代码实现：

void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child< _con.size()){if (child + 1<_con.size() && _con[child + 1]>_con[child]){++child;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent=child  ;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}

5.3 empty

bool empty(){return _con.empty();}

5.4 size

size_t size(){return _con.size();}

5.5 top

const T& top(){return _con.back[0];}

5.6 仿函数实现大小堆

想要大堆改小堆可以直接在代码上面修改，但是要实现大堆，代码又得重新修改。
这里就得用到上面提到的仿函数了。
写两个仿函数，一个实现大堆，一个实现小堆。

大堆实现：

template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}};

小堆实现：

    template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};

在写类模板的时候就把仿函数也一起传过去

template<class T, class Container = vector<T>, class Compare = less<T>>

5.7 实现自定义类型的优先级队列

定义一个日期类：

class Date{public:friend ostream& operator<<(ostream& _cout, const Date& d);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);}private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}

用priority_queue来实现日期排序：

但是如果给的是指针：


传地址每次给的结果不一样。
new不能保证每次new的地址都比前面的大，这里就得重新写一个仿函数。

class GreaterPDate{public:bool operator()(const Date* p1, const Date* p2){return *p1 > *p2;}};

这个时候传地址就不会在变了：

所以说仿函数控制比较逻辑，可以控制用什么去比较。

6. 附模拟实现代码

#pragma once#include<vector>namespace bit{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:void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//if (child + 1 < _con.size() && _con[child] < _con[child + 1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])//if (_con[parent] < _con[child])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){  std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};}

有问题请指出，大家一起进步！！！

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-21/160832.html，文章来源：网络cs，作者：峨乐，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！