产品做网站,宣城市网站集约化建设,吴川网站建设,绵阳手机网站建设#x1f466;个人主页#xff1a;Weraphael ✍#x1f3fb;作者简介#xff1a;目前学习C和算法 ✈️专栏#xff1a;C航路 #x1f40b; 希望大家多多支持#xff0c;咱一起进步#xff01;#x1f601; 如果文章对你有帮助的话 欢迎 评论#x1f4ac; 点赞#x1… 个人主页Weraphael ✍作者简介目前学习C和算法 ✈️专栏C航路 希望大家多多支持咱一起进步 如果文章对你有帮助的话 欢迎 评论 点赞 收藏 加关注✨ 目录 一、priority_queue的介绍二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢三、priority_queue的常见操作四、模拟实现priority_queue4.1 构造函数4.2 删除堆顶元素pop4.3 插入push4.4 获取堆顶元素top4.5 判断是否为空empty4.6 获取个数大小size 五、仿函数5.1 什么是仿函数5.2 实现priority_queue的仿函数 一、priority_queue的介绍 priority_queue是一个容器适配器默认使用vector作为其底层存储数据的容器priority_queue在vector上使用了堆heap的算法将vector中元素构造堆的结构因此priority_queue就是堆。默认情况下是大堆。如何构造成小堆在【仿函数】会讲解到
二、为什么priority_queue不像stack和queue一样使用deque作为其底层存储数据的容器呢
这是因为vector在插入和删除元素时具有较好的性能表现。
在堆中插入新元素时为了保持堆的特性大堆/小堆。则需要通过不断地比较和移动元素来完成。vector作为一个连续的内存块可以更高效地进行元素的插入操作。
相比之下deque在插入和删除操作时需要考虑在数组的两端进行操作头部和尾部并且要进行元素的移动操作使得时间复杂度稍高于vector。
尽管deque在头部和尾部插入/删除操作上有一些优势但对于优先级队列这种需要频繁访问和处理最高优先级元素的场景来说vector更加合适 弹出pop元素若要得到堆顶的元素需要将堆顶元素与最后一个元素交换并重新调整堆使其满足堆的性质。同样由于vector是连续存储的这个操作也可以更高效地进行。 deque的存储空间不是连续的因此在使用时需要更多的空间可能会导致空间的浪费。
三、priority_queue的常见操作 #include iostream
#include queue
using namespace std;// priority_queue的常见操作int main()
{// 默认是大堆priority_queueint 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
{templateclass T, class container vectorTclass 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(){}// 带区间的构造templateclass InputIteratorpriority_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]);// lessint 默认可以不写sort(arr, arr arrSize, lessint());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]);// lessint 默认可以不写sort(arr, arr arrSize, greaterint());for (int i 0; i arrSize; i){cout arr[i] ;}cout endl;return 0;
}【输出结果】 5.2 实现priority_queue的仿函数
namespace wj
{templateclass T, class container vectorT, class Compare lessTclass 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(){}// 带区间的构造templateclass InputIteratorpriority_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
{templateclass T, class container vectorT, class Compare lessTclass 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(){}// 带区间的构造templateclass InputIteratorpriority_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;}
}
