今天博主继续带来STL源码剖析专栏的第四篇博客了！
今天带来优先队列priority_queue的模拟实现！
话不多说，直接进入我们今天的内容！

前言

那么这里博主先安利一下一些干货满满的专栏啦！

手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

优先队列是什么

优先队列的底层实现就是数据结构的堆。其中，小顶堆可以不断更新数组里的最小值，大顶堆可以不断更新数组里的最大值，push和pop自带排序功能，经常用来解决TopK问题。

如果大家有需要数据结构堆的实现可以通过博主的传送门食用噢~

【堆】数据结构-堆的实现【超详细的数据结构教学】https://blog.csdn.net/Yu_Cblog/article/details/124944614

priority_queue的模拟实现

priority_queue底层是默认适配vector的，并且默认是大顶堆。

MyPriorityQueue.h

namespace yufc {template, class Compare = std::less>//默认是less  Compare是一个进行比较的仿函数//less -- 小堆class priority_queue {public:templatepriority_queue(InputIterator first, InputIterator last) {while (first != last) {//不要直接去push，push调用的是向上调整，会慢很多//先弄进数组再建堆快一点，用向下调整_con.push_back(*first);++first;}//建堆for (int i = ((_con.size() - 1 - 1) / 2); i >= 0; i--) {adjust_down(i);}}//如果写了这个构造编译器就不会生成其它类型构造了，所以要自己写priority_queue() {}void adjust_up(size_t child) {Compare cmp;size_t parent = (child - 1) / 2;//找到父亲节点的下标while (child > 0) { //logn//if (_con[child] > _con[parent]) {//if (_con[parent] < _con[child]) {if (cmp(_con[parent],_con[child])) {std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(size_t parent) {Compare cmp;size_t child = parent * 2 + 1;while (child < _con.size()) {//选出左右孩子中大的那个if (child + 1 < _con.size() && cmp(_con[child], _con[child + 1])) {++child;}if (cmp(_con[parent], _con[child])) {std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else break;//已经调整结束了，不用再调整了}}void push(const T& x) {_con.push_back(x);adjust_up(_con.size() - 1);}void pop() {std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top() {//返回值不允许修改 -- 修改了就不是堆了return _con[0];}bool empty() const {return _con.empty();}size_t size() const {return _con.size();}private:Container _con;};
}

测试代码

void test_priority_queue() {yufc::priority_queue,less>pq; //底层是个堆//默认是大顶堆 -- 大的优先级高pq.push(3);pq.push(1);pq.push(2);pq.push(5);pq.push(0);pq.push(1);while (!pq.empty()) {cout << pq.top() << " ";pq.pop();}cout << endl;int a[] = { 1,3,5,7,9,2,4,6,8,0 };yufc::priority_queuepq1(a, a + sizeof(a) / sizeof(int));while (!pq1.empty()) {cout << pq1.top() << " ";pq1.pop();}cout << endl;//priority_queueheap(a, a + sizeof(a) / sizeof(int));//这样构造也可以//如果想控制是小的优先级高呢？//我们要调整第三个模板参数，如果想传第三个，就必须传第二个priority_queue,greater>heap(a, a + sizeof(a) / sizeof(int));//这样构造也可以while (!heap.empty()) {cout << heap.top() << " ";heap.pop();}cout << endl;
}

尾声

看到这里，相信大家对priority_queue的模拟实现已经有一定的了解了！这些容器的模拟实现，是我们掌握STL的开始，后面，博主将会给大家带来map、set、哈希等等STL容器的模拟实现，持续关注，订阅专栏，点赞收藏都是我创作的最大动力。

（转载时请注明作者和出处。未经许可，请勿用于商业用途 )
更多文章请访问我的主页

@背包https://blog.csdn.net/Yu_Cblog?type=blog