priority_queue 优先级队列
堆的概念
STL中的 priority_queue 是数据结构中的堆，堆的本质是一个完全二叉树，而堆又分为大根堆和小根堆。
- 小根堆（min heap）：任意节点的值 ≤ 其子节点的值。
- 大根堆（max heap）：任意节点的值 ≥ 其子节点的值。
我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。不难发现，对于大顶堆（小顶堆），堆顶元素（根节点）的值总是最大（最小）的。
堆的存储结构
堆是一个非线性的树形结构，但是在计算机实现当中，我们往往是采用数组的形式进行存储。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|
在这一段数组中，我们使用公式来判断一个节点的子节点和父节点。
堆节点公式
给定索引i，其左子节点的索引为2 i + 1，右子节点的索引为2 i + 2，父节点的索引为( i − 1 ) / 2（向下整除）。当索引越界时，表示空节点或节点不存在。
如何建堆
给定一个数组，我们要如何才能实现堆的逻辑结构呢？这涉及到建堆操作，堆分为大根堆和小根堆的，堆总是有序的。其实建堆就是把数组中的数据按照堆的逻辑结构（完全二叉树）进行大小排序，就可以完成建堆操作。
那么我们怎样才能实现按照堆的逻辑结构进行排序呢？首先堆是分为大小根堆的，STL 中默认为大根堆，那么我们首先实现大根堆排序建堆。
大根堆是根节点最大，叶子节点最小的排序方式。按照常规排序思想，我们首先从最后一个叶子节点开始排序。
向上调整建堆
在这里我们会遇到一个问题，该怎样进行排序？大根堆最基本的逻辑就是父亲节点的值总是大于子节点的值，所以我们首先比较左右子节点值的大小，比较得出是左子树的值大还是右子树的值大，然后再使用较大的子节点值与父亲节点值进行比较，如果子节点值小于父亲节点值，则不进行任何操作这已经满足堆的逻辑，反之进行值替换，接着将子节点重新赋值为父亲节点，再重新计算父亲节点进入下一轮值比较，直至达到根节点或者子节点值小于父亲节点值时，停止排序。
这是向上调整建堆的思路，但是这个思路有一个致命问题：向上调整是从叶子节点开始，每次只调整一个元素，导致最坏情况下，向上排序建堆的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) 。
向下调整建堆
向下调整的核心思想是从下到上依次调整一个子树。
向下调整思想将数据分为多个子树，每个子树只需向下调整好自己的子树，保证自己一定是一个大根堆，从后往前依次调整（子树 1 -> 子树 2 -> 子树 3），自然地最终我们的堆就排好序了。最终向下调整算法的时间复杂度为 O ( n ) O(n) O(n) 。
template<class T, class Container = vector<T>>
class priority_queue
{
private:// 向上调整算法void AdjustUp(int child){int parent = (child - 1) / 2;while(child > 0 && _con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}// 向下调整算法void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;if (_con[parent] < _con[max_value]){std::swap(_con[parent], _con[max_value]);parent = max_value;child = parent * 2 + 1;}else{break;}}}
public:// 建堆template<class InputIterator>priority_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;
}
STL priority_queue 实现
STL 中堆的实现并不复杂，它和 queue、stack 一样采用了容器适配器的设计，默认容器设置为 vector 。因为 vector 非常适合作为 priority_queue 的底层容器，至于为什么前面已经讨论过原因了。
// priority_queue 默认大根堆
template<class T, class Container = vector<T>>
class priority_queue
{
private:// 向下调整void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){int max_value = child + 1 < _con.size() && _con[child] < _con[child + 1] ? child + 1 : child;if (_con[parent] < _con[max_value]){std::swap(_con[parent], _con[max_value]);parent = max_value;child = parent * 2 + 1;}else{break;}}}// 向上调整void AdjustUp(int child){int parent = (child - 1) / 2;while(child > 0 && _con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}}public:typedef typename Container::iterator iterator;typedef typename Container::const_iterator const_iterator;iterator begin(){return _con.begin();}iterator end(){return _con.end();}priority_queue(){}~priority_queue(){clear();}template<class InputIterator>priority_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(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}void push(const T& value){_con.push_back(value);AdjustUp(_con.size() - 1);}T top() const{return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}void clear(){_con.clear();}void swap(priority_queue& other){std::swap(_con, other._con);}
private:Container _con;
};