C++中priority_queue的實現

C++中priority_queue的實現

優先級隊列相對於普通隊列，提供了插隊功能，每次最先出隊的不是最先入隊的元素，而是優先級最高的元素。

它的實現采用了標准庫提供的heap算法。該系列算法一共提供了四個函數。使用方式如下：

首先，建立一個容器，放入元素：

vector coll;
insertNums(coll, 3, 7);
insertNums(coll, 5, 9);
insertNums(coll, 1, 4);

printElems(coll, "all elements: ");

打印結果為：

all elements: 
3 4 5 6 7 5 6 7 8 9 1 2 3 4

然後我們調用make_heap，這個算法把[beg, end)內的元素建立成堆。

make_heap(coll.begin(), coll.end());

printElems(coll, "after make_heap: ");

打印結果：

after make_heap: 
9 8 6 7 7 5 5 3 6 4 1 2 3 4

然後我們調用pop_heap，這個算法必須保證[beg, end)已經是一個heap，然後它將堆頂的元素（其實是begin指向的元素）放到最後，再把[begin. end-1)內的元素重新調整為heap

pop_heap(coll.begin(), coll.end());
coll.pop_back();
printElems(coll, "after pop_heap: ");

打印結果為：

after pop_heap: 
8 7 6 7 4 5 5 3 6 4 1 2 3

接下來我們調用push_heap，該算法必須保證[beg, end-1)已經是一個heap，然後將整個[beg, end)調整為heap

coll.push_back(17);
push_heap(coll.begin(), coll.end());

printElems(coll, "after push_heap: ");

打印結果為：

after push_heap: 
17 7 8 7 4 5 6 3 6 4 1 2 3 5

最後我們使用sort_heap將[beg, end)由heap轉化為有序序列，所以，前提是[beg, end)已經是一個heap

sort_heap(coll.begin(), coll.end());
printElems(coll, "after sort_heap: ");

打印結果為：

after sort_heap: 
1 2 3 3 4 4 5 5 6 6 7 7 8 17

完整的測試代碼如下：

#include 
#include 
#include 
#include 
using namespace std;

template 
void insertNums(T &t, int beg, int end)
{
    while(beg <= end)
    {
        t.insert(t.end(), beg);
        ++beg;
    }    
}

template 
void printElems(const T &t, const string &s = "")
{
    cout << s << endl;
    for(typename T::const_iterator it = t.begin();
        it != t.end();
        ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}


int main(int argc, char const *argv[])
{
    vector coll;
    insertNums(coll, 3, 7);
    insertNums(coll, 5, 9);
    insertNums(coll, 1, 4);

    printElems(coll, "all elements: ");

    //在這個范圍內構造heap
    make_heap(coll.begin(), coll.end());

    printElems(coll, "after make_heap: ");

    //將堆首放到最後一個位置，其余位置調整成堆
    pop_heap(coll.begin(), coll.end());
    coll.pop_back();
    printElems(coll, "after pop_heap: ");

    coll.push_back(17);
    push_heap(coll.begin(), coll.end());

    printElems(coll, "after push_heap: ");

    sort_heap(coll.begin(), coll.end());
    printElems(coll, "after sort_heap: ");

    return 0;
}

根據以上的算法，我們來實現標准庫的優先級隊列priority_queue，代碼如下：

#ifndef PRIORITY_QUEUE_HPP
#define PRIORITY_QUEUE_HPP

#include 
#include 
#include 

template , 
          typename Compare = std::less >
class PriorityQueue
{
public:
    typedef typename Container::value_type value_type; //不用T
    typedef typename Container::size_type size_type;
    typedef Container container_type;
    typedef value_type &reference;
    typedef const value_type &const_reference;


    PriorityQueue(const Compare& comp = Compare(),
                  const Container& ctnr = Container());
    template 
    PriorityQueue (InputIterator first, InputIterator last,
                   const Compare& comp = Compare(),
                   const Container& ctnr = Container());
    void push(const value_type &val)
    {
        cont_.push_back(val);
        //調整最後一個元素入堆
        std::push_heap(cont_.begin(), cont_.end(), comp_); 
    }

    void pop()
    {
        //第一個元素移出堆，放在最後
        std::pop_heap(cont_.begin(), cont_.end(), comp_);
        cont_.pop_back();
    }

    bool empty() const { return cont_.empty(); }
    size_type size() const { return cont_.size(); }
    const_reference top() const { return cont_.front(); }

private:
    Compare comp_; //比較規則
    Container cont_; //內部容器
};

template 
PriorityQueue::PriorityQueue(const Compare& comp,
                                                    const Container& ctnr)
    :comp_(comp), cont_(ctnr)
{
    std::make_heap(cont_.begin(), cont_.end(), comp_); //建堆
}

template 
template 
PriorityQueue::PriorityQueue (InputIterator first, 
                                                     InputIterator last,
                                                     const Compare& comp,
                                                     const Container& ctnr)
    :comp_(comp), cont_(ctnr)
{
    cont_.insert(cont_.end(), first, last);
    std::make_heap(cont_.begin(), cont_.end(), comp_);
}

#endif //PRIORITY_QUEUE_HPP

我們注意到：

1.優先級隊列內部保存了排序規則，這與map和set是一致的。

2.前面我們提到heap算法除了make_heap之外，都必須保證之前是一個建好的heap，這裡我們在構造函數中調用make_heap，保證了後面的各種heap算法都是合法的。

3.還有一點，如果T與容器的類型不一致，例如PriorityQueue >，那麼我們的value_type優先采用int，畢竟我們操作的對象是容器。

測試代碼如下：

#include "PriorityQueue.hpp"
#include 
using namespace std;

int main(int argc, char const *argv[])
{
    PriorityQueue q;
    q.push(66.6);
    q.push(22.3);
    q.push(44.4);


    cout << q.top() << endl;
    q.pop();
    cout << q.top() << endl;
    q.pop();

    q.push(11.1);
    q.push(55.5);
    q.push(33.3);
    q.pop();

    while(!q.empty())
    {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;


    return 0;
}

http://www.cnblogs.com/inevermore/p/4007130.html