【C++初阶】模拟实现优先级队列priority_queue

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：C++航路
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨

---

一、priority_queue的介绍

• priority_queue是一个容器适配器，默认使用vector作为其底层存储数据的容器
• priority_queue在vector上使用了堆heap的算法将vector中元素构造堆的结构，因此，priority_queue就是堆。默认情况下是大堆。（如何构造成小堆在【仿函数】会讲解到）

二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢

1. 这是因为vector在插入和删除元素时具有较好的性能表现。

在堆中插入新元素时，为了保持堆的特性（大堆/小堆）。则需要通过不断地比较和移动元素来完成。vector作为一个连续的内存块，可以更高效地进行元素的插入操作。

相比之下，deque在插入和删除操作时，需要考虑在数组的两端进行操作（头部和尾部），并且要进行元素的移动操作，使得时间复杂度稍高于vector。

尽管deque在头部和尾部插入/删除操作上有一些优势，但对于优先级队列这种需要频繁访问和处理最高优先级元素的场景来说，vector更加合适

2. 弹出pop元素：若要得到堆顶的元素，需要将堆顶元素与最后一个元素交换，并重新调整堆使其满足堆的性质。同样，由于vector是连续存储的，这个操作也可以更高效地进行。

3. deque的存储空间不是连续的，因此在使用时需要更多的空间，可能会导致空间的浪费。

三、priority_queue的常见操作

#include <iostream>
#include <queue>
using namespace std;// priority_queue的常见操作int main()
{// 默认是大堆priority_queue<int> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);pq.push(0);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;return 0;
}

【输出结果】

注意：优先级队列也是不支持迭代器遍历的！！！

四、模拟实现priority_queue

4.1 构造函数

namespace wj
{template<class T, class container = vector<T>>class priority_queue{	private:void AdjustDown(int 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]){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){// 插入数据while (first != last){_con.push_back(*first);++first;}//  建堆操作 (默认是大堆) for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}private:container _con;};
}

插入一个数据，由于还要保持大堆的性质，如果尾插的结点要比其父结点大，就要进行 向上调整

参考博客：点击跳转

4.2 删除堆顶元素pop

void pop()
{// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);
}

4.3 插入push

void push(const T& val)
{// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);
}

4.4 获取堆顶元素top

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

4.5 判断是否为空empty

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

4.6 获取个数大小size

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

五、仿函数

5.1 什么是仿函数

• 仿函数（函数对象）是一种能够被像函数一样调用的对象。它通常是一个类或者结构体，重载了函数调用运算符 operator(),通过重载这个运算符，我们可以将对象当作函数来使用，实现了类似函数的行为。

• 仿函数可以有自己的状态和成员变量，因此可以在多次调用中保持状态。它可以接受参数，并返回一个值。

例如，定义一个加法仿函数可以这样实现：

struct Add 
{int operator()(const int a, const int b) const {return a + b;}
};int main() 
{Add add;int result = add(3, 5);  // 调用仿函数cout << "add(3, 5) = " << result << endl;return 0;
}

在上面的例子中，Add是一个仿函数，它重载了函数调用运算符 operator()，使得add对象可以像函数一样被调用。通过add(3, 5)，我们可以得到结果8

• 在C++ 中，仿函数是一种灵活且强大的编程工具，常常用于算法和标准库中的函数对象。

就比如说sort函数，默认排的是升序

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默认可以不写sort(arr, arr + arrSize, less<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【输出结果】

less是库里提供的，其作用就是用于小于不等式比较的函数对象类

那么如果想排降序，可以将less替换成greater，这也是库里提供的，其作用是用于大于不等式比较的函数对象类

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int arr[] = { 5,1,4,2,0,3 };int arrSize = sizeof(arr) / sizeof(arr[0]);// less<int> 默认可以不写sort(arr, arr + arrSize, greater<int>());for (int i = 0; i < arrSize; i++){cout << arr[i] << ' ';}cout << endl;return 0;
}

【输出结果】

5.2 实现priority_queue的仿函数

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的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[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare com;int 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;}}}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 pop(){// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};
}

注意：如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供>或者<的重载。

namespace wj
{template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{private:void AdjustDown(int parent){Compare com;// 建大堆// 找左右孩子大的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[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare com;int 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;}}}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 pop(){// 头尾结点交换,删除swap(_con[0], _con[_con.size() - 1]);_con.pop_back();// 然后再建堆AdjustDown(0);}void push(const T& val){// 尾部插入一个_con.push_back(val);// 再建堆AdjustUp(_con.size() - 1);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return  _con.size();}private:container _con;};// 日期类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);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
}