目录

一、priority_queue的使用

priority_queue相关概念

priority_queue的定义方式

二、priority_queue的模拟实现

堆的向上调整算法

堆的向下调整算法

priority_queue的模拟实现

---

一、priority_queue的使用

priority_queue相关概念

这个结构就是我们算法常见的数据结构——优先级队列（也就是堆），这个结构的本质就是封装了一个vector作为底层的容器，然后使用堆的一些算法模拟堆的行为，所以我们使用堆结构一般就是使用priority_queue，但是有的算法题是需要我们手写堆的，所以这个结构还是很有必要模拟实现的。

priority_queue的定义方式

第一种：使用vector作为底层容器，内部使用大根堆。

priority_queue<int, vector<int>, less<int>> q;

第二种：使用vector作为容器，内部使用小根堆。

priority_queue<int, vector<int>, greater<int>> q;

第三种：不指定底层容器和内部的比较器。

priority_queue<int> q;

我们这里默认就是使用的vector为容器，大根堆的结构。

priority_queue的具体使用

各个函数的功能：

操作	priority_queue 函数	功能描述
push	push(value)	向优先队列插入元素，按优先级顺序排列
pop	pop()	移除优先队列中优先级最高的元素
top	top()	获取优先队列中优先级最高的元素（堆顶元素）
empty	empty()	检查优先队列是否为空
size	size()	获取优先队列中元素的数量

举个栗子：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> q;
    q.push(9);
    q.push(5);
    q.push(8);
    q.push(2);
    q.push(4);
    q.push(7);
    q.push(1);
    while(!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
    return 0;
}

测试效果如图：

二、priority_queue的模拟实现

我们实现堆的时候，最重要的就是两个算法，一个是向上调整算法，一个是向下调整算法，我们接下来的算法设计统一使用大根堆的比较逻辑。

堆的向上调整算法

如图就是一个大根堆了：

调整的基本思路如下：

1、将传入的节点和父节点进行比较。

2、如果是父节点的值更大，就把这两个交换一下位置，然后将父节点变成孩子节点，然后继续往上；如果是父节点更小，那么我们就可以停止调整了，因为这个时候我们的树就是大根堆了。

我们这里还是举一个栗子：

我们现在在上面的堆结构中插入一个数据90。

我们将90和它的父节点50进行比较，90要大，于是就和50进行交换，流程继续。

我们的90和父节点70进行比较，还是90大，于是继续交换，流程继续。

我们的90和父节点（根节点）比较还是90大，于是交换，流程继续。

然后我们到了根节点不能往上了，结束。

向上调整算法的代码如下：

void AdjustUp(int child) {
    Compare com;
    int parent = (child - 1) / 2;
    while(child > 0) {
        if(com(_con[child], _con[parent])) {    
            std::swap(_con[child], _con[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }else {
            break;
        }
    }
}

堆的向下调整算法

如图，我想要使用堆的向下调整算法的大前提就是我们的左右两个孩子必须是大堆才行。

调整思路如下：

1、将目标节点和它较大的一个子节点进行比较。

2、我们需要比较目标节点和它左右孩子中那个较大的节点，如果比子节点较大的小，就将目标节点和较大的那个进行交换，并将那个较大的节点作为新的目标节点继续调整，直到触发边界的条件或是发现比较发现比较为目标节点更大则停止。

我们这里还是来举出一个栗子：

我们从根节点开始向下调整，将50和子节点中较大的一个比较，也就是80，发现子节点要大进行交换。

然后我们还是和上面的逻辑一样，将50和70进行交换，继续该流程。

然后我们发现50没有小于它的字节点中的较大的，停止调整。

堆的向下调整算法的代码如下：

void AdjustDown(int parent) {
    Compare com;
    int child = (parent * 2) + 1; // 先假设是左孩子
    while(child < _con.size()) {
        if(child + 1 < _con.size() && com(_con[child], _con[child + 1])) // 如果是右孩子比左孩子大就将孩子设置为右孩子
        {
            child++;
        }
        if(com(_con[parent], _con[child])) {
            std::swap(_con[parent], _con[child]);
        }else {
            break;
        }
    }
}

priority_queue的模拟实现

我们这里的模拟实现的重点就是上面的两个调整算法了，其他的函数的实现就非常简单了。

函数	功能	实现方法
push(const T& value)	向队列中插入元素	使用容器的 push_back，并通过 make_heap 或者 push_heap 维护堆结构
pop()	移除队列中的最大元素	通过 pop_heap 或 heapify 操作移除堆顶元素
top()	返回队列中的最大元素	访问堆顶元素（不移除）
empty()	检查队列是否为空	通过 container.empty() 判断
size()	返回队列中的元素数量	通过 container.size() 返回

实现的代码如下： 

#include <cstddef>
#include <utility>
#include <vector>
#include <iostream>

// 实现两个比较器
template<class T> 
class Less {
    public: 
        bool operator()(const T& x, const T& y) {
            return x < y;
        }
};

template<class T>
class Greater {
    public:
        bool operator()(const T& x, const T& y) {
            return x < y;
        }
};

namespace xywl {
    template<class T, class Container = std::vector<T>, class Compare = Less<T>>
    class priority_queue {
        public:
            `
            void push(const T& x) {
                _con.push_back(x);
                AdjustUp(_con.size() - 1);
            }
            void AdjustDown(int parent) {
                Compare com;
                int child = (parent * 2) + 1; // 先假设是左孩子
                while(child < _con.size()) {
                    if(child + 1 < _con.size() && com(_con[child], _con[child + 1])) // 如果是右孩子比左孩子大就将孩子设置为右孩子
                    {
                        child++;
                    }
                    if(com(_con[parent], _con[child])) {
                        std::swap(_con[parent], _con[child]);
                    }else {
                        break;
                    }
                }
            }
            void pop() {
                std::swap(_con[0], _con[_con.size() - 1]);
                _con.pop_back();
                AdjustDown(0);
            }
            const T& top() {
                return _con[0];
            }
            size_t size() const {
                return _con.size();
            }
            bool empty() const {
                return _con.empty();
            }
        private:
            Container _con;
    };
}