代码小练习二 - 优先队列

继续代码小练习，优先队列，还会有些其他的应用的例子吧。



* Binary Heap

实现上PriorityQueue可以用BinaryHeap结构，也可用于排序。这里的数组下标为方便是从0而没有从1开始算的。

def heapify(lst,i,size=None,less=lambda x,y:x<y):
    left, right = 2*i+1, 2*(i+1)
    size = size if size else len(lst)
    largest = i
    if left<size and less(lst[largest],lst[left]):#lst[left]>lst[largest]:
        largest = left
    if right<size and less(lst[largest],lst[right]):
        largest = right
    if largest!=i:
        lst[i],lst[largest] = lst[largest], lst[i]
        heapify(lst,largest,size=size)
def build_heap(lst):
    for i in range(int(len(lst)/2),-1,-1):
        heapify(lst,i)
def heap_sort(lst):
    build_heap(lst)
    for i in range(len(lst)-1,0,-1):
        lst[0], lst[i] = lst[i], lst[0]
        heapify(lst,0,size=i)
class PriorityQueue:
    def __init__(self,less=lambda x,y:x<y):
        self.less = less
        self.container = list()
    def push(self,x):
        lst = self.container
        parent = lambda x:int((i-1)/2)
        lst.append(x)
        i = len(lst)-1
        p = parent(i)
        while i>0 and self.less(lst[p],lst[i]):
            lst[i],lst[p] = lst[p], lst[i]
            i = p; p = parent(i)
    def pop(self):
        if not self.empty():
            lst = self.container
            x, lst[0] = lst[0], lst[-1]
            lst.pop()
            heapify(lst,0,less=self.less)
            return x
        else:
            raise "underflow"
    def top(self):
        if not self.empty():
            return self.container[0]
        else:
            raise "empty"
    def size(self):
        return len(self.container)
    def empty(self):
        return self.size()==0
        



* Huffman Coding

一个PriorityQueue的实际的例子，用于数据压缩。

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <cstring>
using namespace std;
struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;
    explicit Node(char data,int freq)
        :data(data),freq(freq),left(NULL),right(NULL) {
    }
    explicit Node(Node* left,Node* right)
        :data('\0'),freq(left->freq+right->freq),left(left),right(right) {
    }
    ~Node(){
        if(left)
            delete left;
        if(right)
            delete right;
    }
    bool isLeaf() const {
        return left==NULL or right==NULL;
    }
};
struct NodeCmp {
    bool operator()(const Node* n1,const Node* n2) {
        return n1->freq > n2->freq;
    }
};
Node* huffman_tree(const map<char,int>& entries) {
    priority_queue<Node*,vector<Node*>,NodeCmp> pq;
    for(map<char,int>::const_iterator it=entries.begin(); it!=entries.end(); ++it )
        pq.push(new Node(it->first,it->second));
    int n = entries.size();
    //while(pq.size()>1){
    for(int i=0; i<n-1; i++) {
        Node* x = pq.top();
        pq.pop();
        Node* y = pq.top();
        pq.pop();
        Node* n=new Node(x,y);
        pq.push(n);
    }
    return pq.top();
}
void huffman_count(string text,map<char,int>& result) {
    for(unsigned i=0; i<text.size(); i++)
        result[text[i]]++;
}
void huffman_travel(Node* node,vector<bool>& code,map<char, vector<bool> >& result) {
    if(node->isLeaf())
        result[node->data] = code;
    else {
        {
            vector<bool> left(code);
            left.push_back(false);
            huffman_travel(node->left,left,result);
        }{
            vector<bool> right(code);
            right.push_back(true);
            huffman_travel(node->right,right,result);
        }
    }
}

void huffman_code(Node* tree,map<char, vector<bool> >& result) {
    vector<bool> empty;
    huffman_travel(tree,empty,result);
}
void huffman_print(map<char, vector<bool> >& code) {
    cout<<"dict\n";
    for (map<char, vector<bool> >::iterator i=code.begin() ; i != code.end(); ++i ) {
        cout << i->first << " => ";
        for(vector<bool>::iterator j=i->second.begin(); j!=i->second.end(); ++j) {
            cout <<((*j)?'1':'0');
        }
        cout<<endl;
    }
}
void huffman_print(vector<bool>& code) {
    cout<<"list\n";
    for(unsigned i=0; i<code.size(); i++)
        cout<<code[i];
    cout<<endl;
}
void huffman_print(const char* code) {
    cout<<"string\n"<<code<<endl;
}
Node* huffman_encode(const string& text,map<char, vector<bool> >& dict,vector<bool>& result) {
    map<char,int> entries;
    huffman_count(text,entries);
    Node* tree = huffman_tree(entries);
    huffman_code(tree,dict);
    for(unsigned i=0; i<text.size(); i++) {
        const vector<bool>& append = dict[text[i]];
        copy(append.begin(),append.end(),back_insert_iterator< vector<bool> >(result));
    }
    return tree;
}
void huffman_decode(vector<bool>& code,Node* const tree,string& result) {
    Node* p = tree;
    for(unsigned i=0; i<code.size(); i++) {
        bool bit = code[i];
        p = (bit==false)?p->left:p->right;
        if(p->isLeaf()) {
            result.push_back(p->data);
            p = tree;
        }
    }
}
int main(int argc, char **argv) {
    const char* text = "William Shakespeare (baptised 26 April 1564; died 23 April 1616) was an English poet and playwright, widely regarded as the greatest writer in the English language and the world's pre-eminent dramatist. He is often called England's national poet and the \"Bard of Avon\". His surviving works, including some collaborations, consist of about 38 plays, 154 sonnets, two long narrative poems, and several other poems. His plays have been translated into every major living language and are performed more often than those of any other playwright.";
    map<char, vector<bool> > code;
    vector<bool> encode;
    Node* tree = huffman_encode(text,code,encode);
    huffman_print(code);
    huffman_print(encode);
    cout<<"bit length "<<strlen(text)*sizeof(char)*8<<"->"<<encode.size()<<endl;
    string decode;
    huffman_decode(encode,tree,decode);
    huffman_print(decode.c_str());
    delete tree;
    return 0;