hedgezzz的部落格

"Elements of programming interface"  裡面有一個 sample , 關於  priority queue ,

以下是該範例 :

minheap.hpp :

template <typename T>
class Compare{
public:
    bool operator()(const pair<T,int> &lhs,const pair<T,int> &rhs) const{
        return lhs.first > rhs.first ;
    }
} ;

template <typename T>
vector<T> merge_arrays(const vector<vector<T> > &S)
{
    priority_queue<pair<T,int>,vector<pair<T,int> >,Compare<T> > min_heap;
    vector<int> S_idx(S.size(),0) ;

    for(int i=0;i<S.size();++i)
    {
        min_heap.emplace(S[i][0],i) ;
        S_idx[i] = 1 ;
    } //for

    vector<T> ret ;
    while(!min_heap.empty())
    {
        pair<T,int> p = min_heap.top() ;

        ret.emplace_back(p.first) ;
        if(S_idx[p.second] < S[p.second].size())
        {
            min_heap.emplace(S[p.second][S_idx[p.second]++],p.second) ;
        }
        min_heap.pop() ;
    } //while

    return ret ;
}

priority_queue2.cpp:

int main()
{
    vector<int> v1 ;
    vector<int> v2 ;
    vector<int> v3 ;
    vector<vector<int> > vx ;

    for(int idx=0;idx<30;idx++)
    {
        if( (idx%3)==0)
            v1.push_back(idx) ;
        else if( (idx%3)==1)
            v2.push_back(idx) ;
        else
            v3.push_back(idx) ;
    }//for

    vx.push_back(v1) ;
    vx.push_back(v2) ;
    vx.push_back(v3) ;

    cout <<"v1=" << v1[0]<<" " <<v1[1]<< endl ;
    cout <<"v2=" << v2[0]<<" " <<v2[1]<< endl ;
    cout <<"v3=" << v3[0]<<" " <<v3[1]<< endl ;

    cout << "ready " << endl ;

    vector<int> v = merge_arrays<int>(vx) ;

    cout << "done " << endl ;
    int iret ;
    while(!v.empty())
    {
        iret = v.back() ;
        v.pop_back() ;
        cout << iret << " " ;
    } //while
    cout << endl ;
}

g++ --std=c++0x priority_queue2.cpp -o priority_queue2.exe

output :

v1=0 3
v2=1 4
v3=2 5
ready
done

29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0