PQ使用

priority_queue默认用 < 比较元素，也就是数值大的优先级排列在最前面，最先出队列。那么怎样使它翻转输出呢，书中的例子只是简单的吧key本身的大小作为优先级来使用了，那么这里就要借助一个结构了，用来存储key和priority。
第一次代码比较复杂：
pq.cpp

#include<cstdio>
#include<queue>

using namespace std;

class NODE {
    public:
        char ch;
        int  freq;

        bool operator>(const NODE n1) const
        {
            return (this->freq > n1.freq);
        }

        NODE(char c, int n)
        {
            ch = c;
            freq = n;
        }
};

int main()
{
    priority_queue< NODE, vector<NODE>, greater<NODE> > pq;

    pq.push(NODE('a', 8));
    pq.push(NODE('b', 4));
    pq.push(NODE('c', 5));

    printf("%d %c\n", pq.top().freq, pq.top().ch);
    pq.pop();
    printf("%d %c\n", pq.top().freq, pq.top().ch);

    return 0;
}

第二次简单了一些，pq_v2.cpp:

#include<cstdio>
#include<queue>

using namespace std;

class NODE {
    public:
        char ch;
        int  freq;

        // cos the default priority is from biger one to smaller one
        bool operator<(const NODE n1) const
        {
            return (this->freq > n1.freq);// priority retorate.
        }

        NODE(char c, int n)
        {
            ch = c;
            freq = n;
        }
};

int main()
{
    priority_queue<NODE> pq;

    pq.push(NODE('a', 8));
    pq.push(NODE('b', 4));
    pq.push(NODE('c', 5));

    printf("%d %c\n", pq.top().freq, pq.top().ch);
    pq.pop();
    printf("%d %c\n", pq.top().freq, pq.top().ch);

    return 0;
}

这里用的是模板库提供的pq的模板，它的定义时这个样子的：

In their implementation in the C++ Standard Template Library, priority queues take three template parameters:

1
2

template < class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type> > class priority_queue;

• T: Type of the elements.
• Container: Type of the underlying container object used to store and access the elements.
• Compare: Comparison class: A class such that the expression comp(a,b), where comp is an object of this class and aand b are elements of the container, returns true if a is to be placed earlier than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function. This defaults to less<T>, which returns the same as applying the less-than operator (a<b).
  The priority_queue object uses this expression when an element is inserted or removed from it (using push orpop, respectively) to grant that the element popped is always the greatest in the priority queue.

默认的话只需要提供数据的类型即可，对于基本的数据类型，他是按照less的顺序入队列，出队列的时候是优先级比较大的先出；它默认使用的容器是vector；然后还有less实际上是一个函数对象，它的内部重载了()操作符，相当于一个<号，这里贴出greater的代码理解一下，

1
2
3
4

template <class T> struct greater : binary_function <T,T,bool> {
  bool operator() (const T& x, const T& y) const
    {return x>y;}
};

Members

bool operator() (const T& x, const T& y)

Member function returning the result of the comparison  x>y.

bool operator<(const NODE n1)后面少了一个const，以下是G++出错的提示，一满屏了快。。。：

xi@xi-virtual-machine:1053$ g++ huffman.cpp -o huffman
In file included from /usr/include/c++/4.6/queue:64:0,
                 from huffman.cpp:2:
/usr/include/c++/4.6/bits/stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Item]’:
/usr/include/c++/4.6/bits/stl_heap.h:305:4:   instantiated from ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Item*, std::vector<Item, std::allocator<Item> > >, _Distance = int, _Tp = Item, _Compare = std::less<Item>]’
/usr/include/c++/4.6/bits/stl_heap.h:436:4:   instantiated from ‘void std::make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Item*, std::vector<Item, std::allocator<Item> > >, _Compare = std::less<Item>]’
/usr/include/c++/4.6/bits/stl_queue.h:391:9:   instantiated from ‘std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) [with _Tp = Item, _Sequence = std::vector<Item, std::allocator<Item> >, _Compare = std::less<Item>]’
huffman.cpp:31:26:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:236:22: error: passing ‘const Item’ as ‘this’ argument of ‘bool Item::operator<(Item)’ discards qualifiers [-fpermissive]