文章目录
?priority_queue的介绍和使用? priority_queue的介绍?priority_queue的使用 ?仿函数的使用?C语言有趣的模仿push_back?priority_queue的模拟实现?总结
?priority_queue的介绍和使用
? priority_queue的介绍
priority_queue
官方文档:https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
?priority_queue的使用
优先级队列默认使用vector作为其底层容器存储数据的容器,在vector上又使用堆算法讲vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的成员位置,都可以考虑使用priority_queue。
注意:默认情况下priority_queue是大堆
数说明 | 接口说明 |
---|---|
priority_queue()/priority_queue(first,last) | 构造空的栈 |
empty() | J检测优先级队列是否为空,是返回true,否则返回false |
size() | 返回元素的个数 |
top() | 返回优先级队列中最大(最小元素),即堆顶元素 |
push(x) | 在优先级队列中插入元素 |
pop() | 删除优先级队列中最大(最小)元素,即堆顶元素 |
需要注意的是:
默认情况下,priority_queue
是大堆
如果需要要得到小堆,修改比较方式就好,比较方式可以有仿函数,函数指针,函数模板,类模版等等,
比如使用function
文件的
正常来说,greate是用来降序,大根堆,这里跟往常使用不同,因此,需要注意!!
priority_queue
中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。 #include "Priority_queue.h"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);}bool operator==(const Date& d){return (_year == d._year && _month == d._month && _day == d._day);}bool operator!=(const Date& d){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;}struct PDateless //struct默认为public,comfunc()才能调用,class默认为private{bool operator()(Date* p1, Date* p2){return *p1 < *p2;}};void TestPriorityQueue(){//大堆,需要用户在自定义类型中提供<重载own::priority_queue<Date*, vector<Date*>, PDateless> q1;q1.push(new Date(2024, 9, 13));q1.push(new Date(2024, 9, 14));q1.push(new Date(2024, 9, 15));while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;}int main(){TestPriorityQueue();return 0;}
如 在OJ中的使用数组中的第K个最大元素:https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
class Solution {public:int findKthLargest(vector<int>& nums, int k) {// 将数组中的元素先放入优先级队列中priority_queue<int> p(nums.begin(), nums.end());// 将优先级队列中前k-1个元素删除掉for (int i = 0; i < k - 1; ++i){p.pop();}return p.top();}};
?仿函数的使用
仿函数/函数对象:重载了operator()的类,类的对象可以像函数一样使用operator()
特点,参数个数和返回值根据需求确定,不固定,很灵活
// 定义一个仿函数类class Add {public:// 重载 operator(),接受两个参数并返回它们的和int operator()(int a, int b) {return a + b;}};int main() {// 创建仿函数对象Add add;// 使用仿函数int result = add(3, 4); // 调用 operator()std::cout << "3 + 4 = " << result << std::endl;return 0;}
灵活使用:
class Func{public:void operator()(int n){while (n--){cout << "Func调用" << endl;}cout << endl;}};int main(){//仿函数Func f1;f1(10);f1.operator()(10);return 0;}
?C语言有趣的模仿push_back
void PushBack(int x){printf("void PushBack(int x)\n");}// Cstruct Vector{void(*push_back)(int);int* _a;int _size;int _capacity;};void Init(struct Vector* pv){pv->push_back = PushBack;//...}int main(){Vector v;Init(&v);v.push_back(1);v.push_back(2);return 0;}
?priority_queue的模拟实现
通过对priority_queue
的底层结构就是堆,因此此处只需对对进行通用的封装即可。
#pragma once#include <iostream>#include <vector>#include <algorithm>using namespace std;namespace own{template<class T>struct myless{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct mygreater{bool operator()(const T& x, const T& y){return x > y;}};template <class T,class Container = vector<T>,class Compare = myless<T>>class priority_queue{public://强制编译器生成priority_queue() = default;T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}
使用迭代器添加元素数据进数组:当数据都进vector容器,我们随带建堆:
template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}//从顶开始建堆for (size_t i = 0 ;i < _con.size();++i){adjustup(i);}}
建堆两种方式:向上建堆:向下建堆://第一种void adjustup(size_t child){Compare comfunc;while (child > 0){size_t parent = (child - 1) / 2;if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = child * 2 + 1;}else{break;}}}//第二种void adjustup(int child){Compare comfunc;while (child > 0){size_t parent = (child - 1) / 2;if (comfunc(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;//加不加这个parent都可以,因为上面可以再次获取,加了可以方便理解//parent = (child - 1) / 2;}else{break;}}//}//第三种 //也可以是这样的写法void adjustup(int child){Compare comfunc;size_t parent = (child - 1) / 2;// // 注意:这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致while (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}
向下调整建堆: void adjustdown(int parent){Compare comfunc;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child]))//注意:这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致{swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}
两个操作push
和pop
void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size()-1]);_con.pop_back();adjustdown(0);}
priority_queue的源代码:
#pragma once#include <iostream>#include <vector>#include <algorithm>using namespace std;namespace own{template<class T>struct myless{bool operator()(const T& x, const T& y){return x < y;}};template<class T>struct mygreater{bool operator()(const T& x, const T& y){return x > y;}};template <class T,class Container = vector<T>,class Compare = myless<T>>class priority_queue{public://强制编译器生成priority_queue() = default;//template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}//从顶开始建堆for (size_t i = 0 ;i < _con.size();++i){adjustup(i);}}//void adjustup(size_t child)//{//Compare comfunc;//while (child > 0)//{//size_t parent = (child - 1) / 2;//if (comfunc(_con[parent], _con[child]))//{//swap(_con[parent], _con[child]);//child = parent;//parent = child * 2 + 1;//}//else//{//break;//}//}//}//void adjustup(int child)//{//Compare comfunc;//while (child > 0)//{//size_t parent = (child - 1) / 2;//if (comfunc(_con[parent], _con[child]))//{//swap(_con[child], _con[parent]);//child = parent;////加不加这个parent都可以,因为上面可以再次获取,加了可以方便理解////parent = (child - 1) / 2;//}//else//{//break;//}//}//}//i 为child //也可以是这样的写法void adjustup(int child){Compare comfunc;size_t parent = (child - 1) / 2;// // 注意:这里的parent 和child的顺序要和adjustdown的if (comfunc(_con[parent] , _con[child]))比较顺序一致while (comfunc(_con[parent] , _con[child])) {swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}//i为parentvoid adjustdown(int parent){Compare comfunc;size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && comfunc(_con[child] , _con[child + 1])){++child;}if (comfunc(_con[parent] , _con[child]))//注意:这里的parent 和child的顺序要和adjustupwhile (comfunc(_con[parent] , _con[child]))顺序一致{swap(_con[parent], _con[child]);parent = child;child = 2 * parent + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size()-1]);_con.pop_back();adjustdown(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}