你真的掌握到“优先级队列“的精髓了吗？

前文

如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列这种数据结构。

一，priority_queue的介绍

1.优先级队列是一种容器适配器，根据严格的弱排序标准，他的第一个元素是所有元素中最大的。
2.此结构类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，priority_queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素

5.标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6.需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

二，priority_queue的模拟实现

priority_queue要实现的功能有以下几种：

void adjust_up(int child)//push的时候要用
void adjust_down(int parent)//pop的时候要用
void push(const T& x)//在优先级队列中插入元素x
void pop()//删除优先级队列中最大(最小)元素，即堆顶元素
const T& top()//返回优先级队列中最大(最小元素)，即堆顶元素
size_t size()//返回队列中的有效数据个数
bool empty()//判空

由于底层结构是堆的顺序结构，所有实际上这个模拟实际上就是利用底层容器实现一个堆.

2.1 成员变量

template<class T,class Container=vector<T>，class Compare> 
    class priority_queue
    {
    private:
        Container _con;
    };

这里底层容器的实现我们默认用 vector，这里需要注意的一点是我们这里不需要写构造函数，默认构造函数会自动调用底层容器的构造函数。

2.2 adjust_up()/adjust_down()

我们在简介中提到优先级队列用的堆的结构，默认情况下用的是大堆，而用堆的话，在push和pop的过程中就少不了向上调整和向下调整，因此我们先将这两个函数完成，其他的就很简单。

2.2.1 adjust_up()

adjust_up向上调整，通常用于push，在结尾处push一个值后，通过向上调整，将他调整到该去的位置，这里我们采取的是图文讲解的模式,下面就上图

void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child>0)
            {
                if (_con[parent] < _con[child])
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

2.2.2 adjust_down()

ajust_down向下调整，用于pop，在pop时会解释

adjust_down需要考虑左右孩子的越界问题，这里需要注意

//向下调整
        void adjust_down(int parent)
        {
            int child = parent * 2 + 1;
            while (child < _con.size())
            {
                //看右孩子是否越界，然后取左右孩子大的值
                if (child + 1 < _con.size() && _con[child + 1] > _con[child])
                {
                    child = child + 1;
                }

                if (_con[parent] < _con[child])
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

2.3 push()/pop()

2.3.1 push()

push:在优先级队列中插入元素x
实现逻辑:尾插插入元素x，然后通过adjust_up调整位置，堆的结构不被破坏。

        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size()-1);
        }

2.3.2 pop()

pop:删除优先级队列中最大(最小)元素，即堆顶元素
实现逻辑:队列中的 top和最后一个数据进行交换，然后进行尾删，在对换到top位置的数据进行adjust_down,保证堆的结构不被破坏

        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjust_down(0);
        }

2.4 top()/size()/empty()

这三个接口的实现比较简单,直接用底层容器的接口实现

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

三，priority_queue的精髓

priority_queue的大体框架大致如上，但这并不是它的精髓，那么他的精髓是什么呢？

不知道有没有老铁发现priority_queue的模板参数有三个，而上面的内容只用了前两个，最后一个还没有用，而最后一个就是精髓。
那么它有什么作用呢，众所周知堆分大堆和小堆，大堆top是最大值，小堆top是最小值，而priority_queue也是支持这种转变的，如何实现的呢，就是靠第三个模板参数。

如上图所示就是库中priority_queue第三个参数转为小堆的使用方法，如上可知greater也是一个类，因为他需要传类模板参数，那么greater是什么呢？
这里还需要涉及一个知识点，那就是仿函数。

3.1 仿函数

仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个 operator ()，这个类就有了类似函数的行为，就是一个仿函数类了。

需要注意的是，仿函数也需要实例化.

3.2 构建greater()/less()

greater()/less()的构建和上面类似，不过多了一个模板参数

    template <class T>
    class less//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;
        }
    };

而运用less、greater需要注意，less在库中表示的是大堆，而我们想要使用就需要调整位置,调整成<。

然后就可以套用类函数。

    void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child>0)
            {
                if (_com(_con[parent],_con[child]))//类函数
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        //向下调整
        void adjust_down(int parent)
        {
            int child = parent * 2 + 1;
            while (child < _con.size())
            {
                //看右孩子是否越界，然后取左右孩子大的值
                if (child + 1 < _con.size() && _con[child + 1]>_con[child])
                {
                    child = child + 1;
                }

                if (_com(_con[parent], _con[child]))//类函数
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }