文章目录
- 1. priority_queue介绍
- 2. priority_queue模拟实现
- 3. 适配器与虚函数
大家好！本文会用C++模拟一个基本的priority_queue类，帮助我们更好的理解priority_queue的内置函数的实现与规则。
1. priority_queue介绍
priority_queue被叫做优先队列：
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)，其数据结构类似于大堆。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
- 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
priority_queue数据结构：
2. priority_queue模拟实现
我们先来看看priority_queue需要实现哪些函数：
template <class T,class Container = vector<T>, class Compare = less<T>>class priority_queue{public://构造函数priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last);//容器操作void adjust_up(int child);void adjust_down(int parent);bool empty() const;size_t size() const;const T& top() const;void push(const T& x);void pop();private:Container _c;Compare comp;};
}
priority_queue需要实现的函数很少，而且函数也多为复用 Container类型的内置函数，所以这里不多讲解，直接贴代码。（priority_queue的重点不在它的函数，在本篇的第三个专题）。
构造函数：
//强制编译器生成默认构造函数priority_queue() = default;//支持迭代器构造template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_c.push_back(*first);first++;};for (int i = ((_c.size() - 1 - 1) / 2); i > 0; i--){adjust_down(i);};};
容器操作函数：
//堆的向上调整函数
void adjust_up(int child)
{while(child > 0){int parent = (child - 1) / 2;if (comp(_c[parent], _c[child])){std::swap(_c[parent], _c[child]);child = parent;}else{break;}}
};//堆的向下调整函数
void adjust_down(int parent)
{while (parent > ((_c.size()-1-1)/2)){int child = parent * 2 + 1;if (comp(_c[child + 1],_c[child])&& child + 1 < _c.size()){child++;}if (comp(_c[parent],_c[child])){std::swap(_c[parent], _c[child]);parent = child;}else{break;}}
};
//复用_c的内置empty函数
bool empty() const
{return _c.empty();
};//复用_c的内置size函数
size_t size() const
{return _c.size();
};//复用_c的内置top函数
const T& top() const
{return _c.front();
};//推入一个数，再对其向上调整
void push(const T& x)
{_c.push_back(x);adjust_up(_c.size() - 1);
};//交换头尾元素(头为最大元素)
//对新头元素向下调整
//对新尾元素pop
void pop()
{if (_c.empty()) return;std::swap(_c[0],_c[_c.size() - 1]);_c.pop_back();adjust_down(0);
};3. 适配器与虚函数
在上文我们注意到，priority_queue有两个特别模板参数，是模板的第二个和第三个参数，而且，他们是priority_queue两个参数的类型，那么，他们是什么🤔？
template <class T,class Container = vector<T>, class Compare = less<T>>
{//...private:Container _c;Compare comp;
}
我们一个一个说。
第二个模板参数-适配器：在C++中，Container叫做 适配器，它的缺省值是一个模板容器，在 priority_queue中，他的默认适配器就是vector。在整个 priority_queue的模拟实现中，所有的函数都是围绕这个适配器容器进行的，可以看作把vector的数据结构量身定做成堆的数据结构，本身堆就是可以用数组实现的。
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。在priority_queue里，当然可以传入自己设计的接口容器。
第二个模板参数-虚函数：在C++中，有一种模板类当做模板参数传入，像函数一样被使用，这样的模板类被称为虚函数，它实际上是类而不是函数。
当然上文留给个悬念，就是没有去实现这个less类。虚函数的实现有一定的规则，现在我们来实现less类：
template<class T>
class less
{
public://类中只有一个()的运算符重载，这个函数用来做判断bool operator()(const T& a, const T& b){return a > b;}
};
虚函数的实现大概就是这样的模式，然后这个类就可以像函数一样使用。
因为priority_queue默认是大堆，所以默认判断规则为less类，当然，如果要实现小堆也是可以的，就要实现一个greater类，并像参数一样传入：
//greater类
template<class T>
class greater
{
public:bool operator()(const T& a, const T& b){return a < b;}
};
//声明
priority_queue<int,vector<int>,greater<int>> x;
由此全部完成，附上总代码图：
#pragma oncenamespace bit
{template<class T>class less{public:bool operator()(const T& a, const T& b){return a > b;}};template<class T>class greater{public:bool operator()(const T& a, const T& b){return a < b;}};template <class T,class Container = vector<T>, class Compare = less<T>>class priority_queue{public:priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_c.push_back(*first);first++;};for (int i = ((_c.size() - 1 - 1) / 2); i > 0; i--){adjust_down(i);};};bool empty() const{return _c.empty();};size_t size() const{return _c.size();};const T& top() const{return _c.front();};void push(const T& x){_c.push_back(x);adjust_up(_c.size() - 1);};void pop(){if (_c.empty()) return;std::swap(_c[0],_c[_c.size() - 1]);_c.pop_back();adjust_down(0);};void adjust_up(int child){while(child > 0){int parent = (child - 1) / 2;if (comp(_c[parent], _c[child])){std::swap(_c[parent], _c[child]);child = parent;}else{break;}}};void adjust_down(int parent){while (parent > ((_c.size()-1-1)/2)){int child = parent * 2 + 1;if (comp(_c[child + 1],_c[child])&& child + 1 < _c.size()){child++;}if (comp(_c[parent],_c[child])){std::swap(_c[parent], _c[child]);parent = child;}else{break;}}};private:Container _c;Compare comp;};
}
本文就到这里，感谢你看到这里❤️❤️！
我知道一些人看文章喜欢静静看，不评论🤔，但是他会点赞😍，这样的人，帅气低调有内涵😎，美丽大方很优雅😊，明人不说暗话，要你手上的一个点赞😘！
