STL之优先级队列priority_queue

超、凢脫俗 2022-09-22 15:59 223阅读 0赞

priority\_queue是一个拥有权值观念的queue，它允许加入新元素，移除旧元素，审视元素值。  
由于是个queue，所以只允许低端加入元素，并从顶端取出元素。

缺省情况下priority\_queue利用一个max-heap完成，后者是一个以vector表现的完全二叉树。  
最大堆可以满足priority\_queue所需要的“依权值高低自动递减排序”的特性。

--------------------

priority\_queue定义：

template <class T, class Sequence = vector<T>, 
                class Compare = less<typename Sequence::value_type> >
    class priorrty_queue
    {
    public:
        typedef typename Sequence::value_type;
        typedef typename Sequence::size_type size_type;
        typedef typename Sequence::reference reference;
        typedef typename Sequence::const_reference const_reference;
    
    protected:
        Sequence c;        //底层容器 顺序表
        Compare comp;   //元素大小比较标准
    
    public:
        priorrty_queue() : c(){}
    
        explicit priorrty_queue(const Compare& x)
            : c(), comp(x)
        {}
    
        template <class InputIterator>
        priorrty_queue(InputIterator first, InputIterator last, const Compare& x)
            : c(first, last), comp(x)
        {
            make_heap(c.begin(), c.end(), comp);
        }
    
        bool empty() const
        {
            return c.empty();
        }
    
        size_type size() const {
            return c.size()
        }
    
        const_reference top() const{
            return c.front();
        }
    
        void push(const value_type& x)
        {
            _STL_TRY{
                c.push_back(x);
                push_heap(c.begin(), c.end(), comp);
            }
            _STL_UNWIND(c.clear());
        }
    
        void pop()
        {
            _STL_TRY
            {
                pop_heap(c.begin(), c.end(), comp);
                c.pop_back();
            }
            _STL_UNWIND(c.clear());
        }
    };

--------------------

因为所有priority\_queue元素进出有一定规则，只有顶端元素才有机会被外界取用，priority\_queue不提供遍历功能，也不提供迭代器。

程序演示：

#include <queue>
    #include <algorithm>
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };
        priority_queue<int> ipq(ia, ia + 9);
        cout << "size = " << ipq.size() << endl;
    
        for (int i = 0; i < ipq.size(); ++i){
            cout << ipq.top() << ' ';
        }
        cout << endl;
    
        while (!ipq.empty())
        {
            cout << ipq.top() << " ";
            ipq.pop();
        }
    
        cout << endl;
    
        system("pause");
    }
    
    /*
    size = 9
    9 9 9 9 9 9 9 9 9
    9 8 5 4 3 3 2 1 0
    请按任意键继续. . .
    */