C++ 适配器 priority_queue(优先级队列)
在了解优先级队列之前，我们要知道它其实就是堆。
数据结构堆讲解
数据结构——堆-CSDN博客大家可以看这一篇我写的博客来详细了解堆的结构、用途、实现。
priority_queue的相关函数
适配器的函数都少，基本上都是这几个。
构造函数
我总结下来就是可以用迭代器构造，可以用拷贝构造，可以用右值引用，可以用其他容器的数据进行构造。并可以和用迭代器和容器的引用它们一起的值进行构造，这个可以给大家举个例子理解一下
其他函数
这些函数都是很常见的，结合上面的例子我们就可以理解。
priority_queue的实现
建堆快慢的问题
在实现之前，我还要再问一下大家一个重要的问题。我们建堆是每push一次后进行向上调整算法快一些，还是我们一次性把所有数据都拷贝过来用log(N)次向上调整算法快一些，还是我们同样一次性拷贝，但是用向下调整算法快一些？
我们首先来分析一下push一个向上调整一个的算法，那么会调整N次，每次向上调整是logN次，那么就是N*logN的时间复杂度。其他两中我在数据结构——堆-CSDN博客里面讲过，这里如果大家懒得去跳转找我CV一下：
向上调整建堆时间复杂度
这里我们现直接看最后一行，DEFG。如果扩展到N，那么最后一行就是N/2个数据，并且最后一行的向上调整时间复杂度刚好是logN，所以最后一行所有建好堆就是N/2*logN的时间复杂度了，那么已经是N*logN的量级了。我们再看前面的数据，因为度为0的节点等于度为2的节点加一，并且前面的向上调整是小雨logN的，所以前面的加起来是总体小于N/2*logN的，总体就小于N*logN。但又大于N/2*logN。所以时间复杂度就是N*log（N）。
向下调整建堆时间复杂度
这里我们就可以直接看出优势了，直接把最后一排N/2的数据全部略过了，只要操作N/2次向下调整算法就行了。
我用草稿纸把过程写一下：
可能化简的系数等有问题，但是我们算的是级数有哪些，最终最大级数就是N，那么时间复杂度就是O(N)。
那么加上入N个数据的时间复杂度就还是N，所以我们采用一次性把所有数据都拷贝过来用log(N)次向下调整算法快一些
代码实现
#pragma once
#include<utility>
#include<algorithm>
#include<vector>
namespace dgj {template <class T,class container=std::vector<T>,class compare =std::less<T>>class priority_queue {public:priority_queue() {}template <class aliterator>priority_queue(aliterator begin,aliterator end,compare pare=compare(), container& x = container()):_con(x),_pare(pare){_con.insert(_con.end(), begin, end);make_heap();}bool empty() {return _con.empty();}T& top() {return _con.front();}void pop() {std::swap(_con.front(), _con.back());_con.pop_back();heap_ajust_down(0);}void push(const T& val) {_con.push_back(val);heap_ajust_up( size() - 1);}size_t size() {return _con.size();}private:void heap_ajust_up(int pos) {int child = pos, parent = (child - 1) / 2;while (child > 0) {if (_pare(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);;child = parent;parent = (child - 1) / 2;}else break;}}void heap_ajust_down(int pos) {int parent = pos, child = parent * 2 + 1;while (child < _con.size()) {if (child + 1 < _con.size() && _pare(_con[child], _con[child + 1]))++child;if (_pare(_con[parent], _con[child])) {std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else break;}}void make_heap() {for (int x = (_con.size() - 2) / 2; x >= 0; --x)heap_ajust_down(x);}container _con;compare _pare;};
}检测
可以用以上的代码进行检测看是否有问题。