c/c++|【C++】优先级队列priority_queue模拟实现&&仿函数 c

往期回顾：上一篇文章已经模拟实现过stack和queue，三者都是容器适配器Container adaptors
stack&&queue&&deque

文章图片

文章目录

前言
大致框架
模拟实现
- size、top、empty
- push插入
- pop删除
- 构造函数
- 测试
仿函数
测试
源码

前言

优先级队列：根据严格的弱排序标准，第一个元素总是优先级最高的，而优先级是相对而言的，并不是大的数优先级就高，就成绩而言100比90高，但A比B高。
priority_queue的底层是一个堆，默认是大堆，堆顶的元素（最大的数）优先级最高

文章图片
因为堆是完全二叉树，默认是由vector实现的，Compare是一个仿函数，用来控制priority_queue的优先级，默认为less(大堆)，也可以传greater变为小堆

文章图片

大致框架

文章图片

我们先不管仿函数，只定义两个模板参数实现成大堆

#pragma once #include #include using namespace std; namespace king { template> class priority_queue { public: //迭代器区间初始化的构造函数 template priority_queue(InputIterator first,InputIterator last) :_con(first,last) {} //无参的构造函数 priority_queue() {} //插入（尾插） void push(const T& x); //删除（变相头删，交换头尾再尾删） void pop(); //返回容器有效元素个数 size_t size() const; //返回堆顶元素 T& top(); //判空 bool empty(); private: Container _con; //默认是vector _con; }; }

模拟实现 size、top、empty

因为priority_queue是容器适配器，所以直接调用其他容器的接口即可

size_t size() const { return _con.size(); } T& top() { return _con[0]; } bool empty() { return _con.empty(); }

相关文章：
堆的模拟实现
因为是底层是一个堆，所以主要的两个函数就是向上调整和向下调整

push插入

void AdjustUp(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { //因为是大堆，所以孩子大于父亲就交换std::swap if (_con[child] > _con[parent]) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else break; } } void push(const T& x) { _con.push_back(x); //直接调用容器_con的push_back AdjustUp(size()-1); }

pop删除

void AdjustDown(size_t parent) { size_t child = parent * 2 + 1; //左孩子 while (child < size()) { //判断是否有右孩子，且右孩子大于左孩子 if (child + 1 < size() && _con[child + 1] > _con[child]) ++child; if (_con[child] > _con[parent]) swap(_con[parent], _con[child]); else break; parent = child; child = parent * 2 + 1; } } void pop() { //头尾交换再尾删（头删） swap(_con[size() - 1], _con[0]); _con.pop_back(); AdjustDown(0); }

构造函数

用迭代器区间初始化，插入到_con容器后，需要把它变成一个大堆，所以从最后一个非叶子节点（最后一个叶子节点的父亲）开始向下调整
相关文章：TopK问题和堆排序

//_con在初始化列表就会自动调用它的默认构造函数初始化 priority_queue() {} template priority_queue(InputIterator first, InputIterator last) :_con(first, last) { size_t lastchild = size() - 1; size_t parent = (lastchild - 1) / 2; for (size_t i = parent; i >= 0; i--) { AdjustDown(i); } }

测试

void priority_test1() { priority_queue pq; pq.push(40); pq.push(30); pq.push(56); pq.push(26); pq.push(45); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; }

默认是大堆，大的优先级高

文章图片

仿函数

【c/c++|【C++】优先级队列priority_queue模拟实现&&仿函数】仿函数本质就是类重载了一个operator()，创建一个行为类似函数的对象，我们可以通过这个对象调整优先级队列是大堆还是小堆，调用STL中的仿函数需要包头文件#inclide

文章图片
和C语言的函数指针类似，qsort就需要一个函数指针来判定排升序还是降序，但仿函数比函数指针更加灵活。当然这只是最基本的仿函数，之后的文章也会深入介绍

struct Less { bool operator()(const int& a, const int& b) const { return a < b; } }; struct Greater { bool operator()(const int& a, const int& b)const { return a > b; } }; int main() { //Less->仿函数类型 ls->仿函数对象 Less ls; //ls.operator()(1,2) cout << ls(1, 2) << endl; cout << Greater()(1, 2) << endl; //匿名对象 }

文章图片

我们就可以根据仿函数Compare是less还是greater，调整向上和向下调整算法，进而实现大小堆的切换

文章图片

文章图片
向下调整也是如此，这样就可以传greater建小堆了

测试

文章图片

源码 priority_queue.h

#pragma once #include #include using namespace std; namespace king { template struct less { bool operator()(const T& a, const T& b) { return a < b; } }; template struct greater { bool operator()(const T& a, const T& b) { return a > b; } }; template, class Compare=less> class priority_queue { private: Compare com; void AdjustUp(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { //if (_con[child] > _con[parent])->父亲小于孩子就调整 if (com(_con[parent], _con[child]))// { swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else break; } } void AdjustDown(size_t parent) { size_t child = parent * 2 + 1; while (child < size()) { //if (child + 1 < size() && _con[child + 1] > _con[child]) if (child + 1 < size() &&com(_con[child], _con[child + 1])) ++child; //if (_con[child] > _con[parent]) if (com(_con[parent], _con[child])) swap(_con[parent], _con[child]); else break; parent = child; child = parent * 2 + 1; } } public: priority_queue() {} template priority_queue(InputIterator first, InputIterator last) :_con(first, last) { size_t lastchild = size() - 1; size_t parent = (lastchild - 1) / 2; for (size_t i = parent; i >= 0; i--) { AdjustDown(i); } } void push(const T& x) { _con.push_back(x); AdjustUp(size() - 1); } void pop() { swap(_con[size() - 1], _con[0]); _con.pop_back(); AdjustDown(0); } size_t size() const { return _con.size(); } T& top() { return _con[0]; } bool empty() { return _con.empty(); } private: Container _con; }; void priority_test1() { priority_queue pq; pq.push(40); pq.push(30); pq.push(56); pq.push(26); pq.push(45); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; } void priority_test2() { priority_queue, greater> pq; pq.push(40); pq.push(30); pq.push(56); pq.push(26); pq.push(45); cout << "greater建小堆-->"; while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; priority_queue pq2; pq2.push(40); pq2.push(30); pq2.push(56); pq2.push(26); pq2.push(45); cout << "默认less建大堆-->"; while (!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } cout << endl; } }

test.cpp