优先队列

优先队列

优先队列是一个特殊的队列，普通队列是先进先出(FIFO)的，而优先队列是根据元素的大小（优先级）决定元素的出队顺序。

C++ STL的优先队列

#include <queue>
#include <iostream>

int main()
&#123;
    std::priority_queue<int> pq;
    pq.push(1);
    pq.push(10);
    pq.push(20);
    pq.push(18);
    pq.push(3);
    pq.push(12);

    int size = pq.size();

    for (int i=0; i < size; i++)
    &#123;
        std::cout<<pq.top()<<' ';
        pq.pop();
    &#125;
    std::cout<<std::endl;
    return 0;
&#125;

# 运行结果:
20 18 12 10 3 1

priority_queue默认是从大到小排序，是因为priority_queue使用了一个默认的比较行为，下面介绍如何自定义比较行为从而按照我们的意愿得到想要的结果。

自定义比较行为

函数对象

先让我们看一下优先队列在STL中的说明。

/**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup sequences
   *
   *  @tparam _Tp  Type of element.
   *  @tparam _Sequence  Type of underlying sequence, defaults to vector<_Tp>.
   *  @tparam _Compare  Comparison function object type, defaults to
   *                    less<_Sequence::value_type>.
   */
    template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    &#123;&#125;

可以看到priority_queue类模板实际有三个参数.

1. _Tp: 元素类型,就是我们存放在优先队列中的元素类型。
2. _Sequence: 元素序列, 默认是vector<_Tp>。
3. _Compare: 比较函数对象, 默认是less<_Sequence::value_type>。

前两个模板参数很好理解，第三个参数比较特殊，_Compare 是一个函数对象（也叫仿函数）。函数对象是一个行为类似于函数的对象，也是通过类来定义的。函数对象可以使得函数功能更加的泛化，STL的算法中很多都使用了函数对象，允许用户可以通过函数对象自定义函数的行为。比如：sort函数接收一个函数对象允许自定义比较行为。

priority_queue默认的函数对象是less，less的定义如下：

/// One of the @link comparison_functors comparison functors@endlink.
template<typename _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
&#123;
    _GLIBCXX14_CONSTEXPR
    bool
    operator()(const _Tp& __x, const _Tp& __y) const
    &#123; return __x < __y; &#125;
&#125;;

less就是一个函数对象类，其继承了binary_function。类内自定义了一个函数operate()，所有的函数对象都是通过operate()发挥作用的。在以函数对象为参数的函数内部通过调用函数对象的operate()方法实现函数行为的泛化。

void algorithm(arg1, arg2,..,,functorObj)
{
    ...
    functorObj();
    ...
}

通过functorObj() 便可以调用函数对象的operate()方法，这种语法类似于Python
的callable对象（定义了 \_\_call\_\_ 方法的对象）。我们通过重写operate()或者编写新的operate()方法就可以定制算法的行为。

使用STL定义的函数对象

STL标准库定义了多个用于比较的函数对象，如less、less_equal、greater、greater_equal等

std::priority_queue<int, std::vector<int>, greater<int>> pq;    //从小到大的优先队列
std::priority_queue<int, std::vector<int>, less<int>> pq;    //从大到小的优先队列

因为priority_queue定义的最后两个参数都是默认参数，如果需要传入第三个参数，那么第二参数也需要传入。

重载比较运算符

我们可以看到less等函数对象都是通过模板实现的，且在operate()方法使用的是比较运算符。因此可以通过重载类的比较运算符定制priority_queue的行为。

struct Test
{
    int num;
    char c;

    bool operator > (const Test& obj) const
    {
        return this->num > obj.num;
    }

    bool operator < (const Test& obj) const
    &#123;
        return this->num < obj.num;
    &#125;

&#125;Test;

int main()
&#123;
    priority_queue<Test, vector<Test>, less<Test>> pq1;
    priority_queue<Test, vector<Test>, greater<Test>> pq2;

    return 0;
&#125;

自定义函数对象

因为priority_queue第三个参数需要的是一个函数对象，我们可以定义自己定义一个函数对象定制priority_queue的行为。

//函数对象QueueCmp
struct QueueCmp
{
    bool operator()(const vector<int> &v1, const vector<int> &v2)const
    &#123;
        return v1[0] > v2[0];
    &#125;
&#125;;

int main()
&#123;
    priority_queue<vector<int>, vector<vector<int>>, QueueCmp> pq;

    return 0;
&#125;

自己实现优先队列

优先队列实际上是一个堆, 在STL中,优先队列默认是一个大顶堆, 从排序角度看, 就是降序排序(从大到小)，因此可以通过堆的相关算法实现优先队列。

#include <iostream>
#include <vector>
#include <cmath>

template<class T>
class PriorityQueue
&#123;
private:
    std::vector<T> data;

public:
    PriorityQueue()
    &#123;

    &#125;

    bool empty() const 
    &#123;
        return data.size()? false:true;
    &#125;

    int size() const 
    &#123;
        return data.size();
    &#125;

    T top() const 
    &#123;
        if (!this->empty())
        &#123;
            return this->data[0];
        &#125;

        return 0;
    &#125;

    void push(T data)
    &#123;
        this->pushHeap(data);
    &#125;

    void pop()
    &#123;
        this->popHeap();
    &#125;

private: 
    void popHeap()
    &#123;
        this->data.erase(this->data.begin());    //delete the top 
        this->adjustHeap(0, this->data.size());    //adjust heap 
    &#125;

    void adjustHeap(int i, int length)
    &#123;
        for(int child = 2*i+1; child < length; child = 2*i+1)
        &#123;
            if(child + 1 < length && this->data[child+1] > this->data[child])
            &#123;
                child += 1;
            &#125;
            if(this->data[child] > this->data[i])
            &#123;
                this->swap(this->data[child], this->data[i]);
                i = child;
            &#125;
            else 
            &#123;
                break; // adjust over 
            &#125;
        &#125;
    &#125;

    void pushHeap(T data)
    &#123;
        this->data.push_back(data);
        int end = this->data.size()-1;  

        for(int i=floor(end*0.5 - 0.5); i>=0; i=floor(i*0.5 - 0.5))
        &#123;
            this->adjustHeap(i, end+1);
        &#125;
    &#125;

    void swap(T &a, T &b)
    &#123;
        T temp = a;
        a = b;
        b = temp;
    &#125;
&#125;;


int main()
&#123;
    PriorityQueue<int> pq;

    pq.push(1);
    pq.push(10);
    pq.push(20);
    pq.push(18);
    pq.push(3);
    pq.push(12);

    int size = pq.size();

    for (int i=0; i < size; i++)
    &#123;
        std::cout<<pq.top()<<' ';
        pq.pop();
    &#125;
    std::cout<<std::endl;
    return 0;
&#125;