[C++]priority_queue的介绍及模拟实现

目录

priority_queue的介绍及模拟实现：：

                                                        priority_queue的介绍

                                                        priority_queue的定义方式

                                                        priority_queue各个接口的使用

                                                        堆的向上调整算法

                                                        堆的向下调整算法

                                                        仿函数

                                                        priority_queue的模拟实现

                                                        反向迭代器的底层原理

                                                        反向迭代器的模拟实现

priority_queue的介绍及模拟实现：：

priority_queue的介绍

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

#include <queue>
int main()
{priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

#include <functional>
#include <queue>
int main()
{priority_queue<int,vector<int>,greater<int>> pq;pq.push(3);pq.push(1);pq.push(2);pq.push(5);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

priority_queue的定义方式

方式一：使用vector作为底层容器，内部构造大堆结构

priority_queue<int,vector<int>,less<int>> pq1;

方式二：使用vector作为底层容器，内部构造小堆结构

priority_queue<int,vector<int>,greater<int>> pq2;

方式三：不指定底层容器，默认为大堆结构

priority_queue<int> pq3;

priority_queue各个接口的使用

priority_queueOJ：数组中第K大的元素

//方法一:建大堆 再popK次
class Solution 
{
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(), nums.end());while (--k){pq.pop();}return pq.top();}
};
//方法二:建K个数的小堆 和堆顶数据比较
class Solution
{
public:int findKthLargest(vector<int>& nums, int k){priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);for (size_t i = k; i < nums.size(); ++i){if (nums[i] > pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
};

堆的向上调整算法

思想：

1.将目标结点与父结点进行比较

2.若目标结点的值比父节点的值大，则交换目标结点与其父节点的位置，并将原目标节点的父节点当作新的目标节点继续进行向上调整，若目标节点的值比其父节点的值小，则停止向上调整。

void AdjustUp(vector<int>& v, size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){if (v[child] > v[parent]){swap(v[child], v[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

堆的向下调整算法

思想：

1.将目标节点与其较大的子节点进行比较

2.若目标节点的值比其较大的子节点的值小，则交换目标节点与其较大的子节点的位置，并将原目标节点的较大子节点当作新的目标节点继续进行向下调整，若目标节点的值比其较大子节点的值大，则停止向下调整。

void AdjustDown(vector<int>& v, int n , size_t parent)
{size_t child = 2 * parent + 1;while (child < v.size()){if (child + 1 < n && v[child] < v[child + 1]){++child;}if (v[parent] < v[child]){std::swap(v[child], v[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

仿函数

仿函数的介绍：

namespace wjq
{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;}};
}
int main()
{wjq::less<int> lessFunc;lessFunc(1, 2);return 0;
}

仿函数的使用场景：

bool cmp(int x, int y)
{return y > x;
}
void BubbleSort(int* a, int n, bool(*pcom)(int, int))
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (pcom(a[j - 1] , a[j])){std::swap(a[j - 1], a[j]);exchange = 1;}}if (exchange == 0){break;}}
}
int main()
{int a[] = { 2,3,4,5,6,1,4,9 };BubbleSort(a, 8, cmp);for (size_t i = 0; i < 8; i++){cout << a[i] << " ";}cout << endl;return 0;
}

namespace wjq
{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 Compare>
void BubbleSort(T* a, int n, Compare com)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (com(a[j], a[j - 1])){std::swap(a[j - 1], a[j]);exchange = 1;}}if (exchange == 0){break;}}
}
int main()
{wjq::less<int> lessFunc;int a[] = { 2,3,4,5,6,1,4,9 };BubbleSort(a, 8, lessFunc);for (size_t i = 0; i < 8; i++){cout << a[i] << " ";}cout << endl;return 0;
}

仿函数的特殊使用场景：

如果在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& out, const Date& d){out << d._year << "-" << d._month << "-" << d._day;return out;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{// 大堆，需要用户在自定义类型中提供<的重载priority_queue<Date> q1;q1.push(Date(2023, 12, 1));q1.push(Date(2023, 12, 2));q1.push(Date(2023, 11, 30));cout << q1.top() << endl;// 如果要创建小堆，需要用户提供>的重载priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2023, 12, 1));q2.push(Date(2023, 12, 2));q2.push(Date(2023, 11, 30));cout << q2.top() << endl;
}
int main()
{TestPriorityQueue();return 0;
}

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& out, const Date& d){out << d._year << "-" << d._month << "-" << d._day;return out;}
private:int _year;int _month;int _day;
};
void TestPriorityQueue()
{//大堆priority_queue<Date*> q1;q1.push(new Date(2023, 12, 1));q1.push(new Date(2023, 12, 2));q1.push(new Date(2023, 11, 30));cout << q1.top() << endl;//小堆priority_queue<Date*> q2;priority_queue<Date*, vector<int>, greater<Date>> q2;q2.push(new Date(2023, 12, 1));q2.push(new Date(2023, 12, 2));q2.push(new Date(2023, 11, 30));cout << q2.top() << endl;
}
int main()
{TestPriorityQueue();return 0;
}

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& out, const Date& d){out << d._year << "-" << d._month << "-" << d._day;return out;}
private:int _year;int _month;int _day;
};
struct PDateLess
{bool operator()(const Date* d1, const Date* d2){return *d1 < *d2;}
};
struct PDateGreater
{bool operator()(const Date* d1, const Date* d2){return *d1 > *d2;}
};
void TestPriorityQueue()
{//大堆priority_queue<Date*, vector<Date*>, PDateLess> q1;q1.push(new Date(2023, 12, 1));q1.push(new Date(2023, 12, 2));q1.push(new Date(2023, 11, 30));cout << *q1.top() << endl;//小堆priority_queue<Date*, vector<Date*>, PDateGreater> q2;q2.push(new Date(2023, 12, 1));q2.push(new Date(2023, 12, 2));q2.push(new Date(2023, 11, 30));cout << *q2.top() << endl;
}
int main()
{TestPriorityQueue();return 0;
}

priority_queue的模拟实现

namespace wjq
{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 = std::vector<T>, class Compare = less<int>>class priority_queue{private:void AdjustUp(size_t child){Compare com;//构造一个仿函数对象size_t parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(size_t parent){Compare com;//构造一个仿函数对象size_t child = 2 * parent + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}public://无参构造函数priority_queue(){//默认构造函数即可}//迭代器区间构造template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){AdjustDown(i);}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);//从size-1开始调整}void pop(){std::swap(_con[0], _con[_con.size() - 1]);//交换首尾数据_con.pop_back();//尾删AdjustDown(0);}const T& top() const{return _con[0];}bool empty() const{return _con.empty();}size_t size()const{return _con.size();}private:Container _con;};
}

反向迭代器的底层原理

反向迭代器的本质就是对正向迭代器的封装，它同样是一个适配器。

STL源码中的反向迭代器的实现：反向迭代器用正向迭代器进行构造。

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
reverse_iterator rbegin() 
{ return reverse_iterator(end());
}
reverse_iterator rend() 
{ return reverse_iterator(begin());
}

STL源码中，其实正向迭代器和反向迭代器的位置是对称的。通过图示，rbegin()迭代器是最后一个数据的下一个位置，但是通过rbegin()访问的数据应该是6，这是通过运算符重载operator*()来解决。

template <class Iterator, class Ref, class Ptr>
Ref operator*()
{Iterator tmp = _it;return *(--tmp);
}

反向迭代器的模拟实现

namespace wjq
{template <class Iterator, class Ref, class Ptr>class ReverseIterator{public:RevserseIterator(Iterator it)//使用正向迭代器构造反向迭代器:_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}typedef ReverseIterator<Iterator, Ref, Ptr> SelfSelf& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s) const{return _it != s._it;}private:Iterator _it;//底层是传入类型的迭代器};
}