C++ STL 优先队列及其霍夫曼编码应用示例 - c++编程基础

优先队列(priority queue)

优先队列是一种比较常用的结构,普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。

当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出（largest-in，first-out）的行为特征。

c++ priority_queue

STL priority_queue是拥有权值观念的queue，它允许在底端添加元素、在顶端去除元素、删除元素。优先级队列内部的元素并不是按照添加的顺序排列，

而是自动依照元素的权值排列, 权值最高者排在最前面。缺省情况下，优先级队列利用一个大顶堆完成。

其实 priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现，算是堆的应用的扩展形式。下面先写一个用 STL 里面堆算法实现

的与真正的STL里面的 priority_queue 用法相似的 priority_queue，加深对 priority_queue 的理解,关于STL堆相关算法参见。

代码如下：

#include  
  
   
#include 
   
     #include 
    
      using namespace std; // 自定义优先级队列 template 
     
       class priority_queue_ { private: vector
      
        data_vec;//存放元素的容器 public: // 默认构造函数 ** priority_queue_() { data_vec = vector
       
        (); } // 带参数的构造函数 priority_queue_(ElemType *data, const int n); //判断优先队列是否为空 bool empty() { return data_vec.empty(); } //返回优先级队列大小 size_t size() { return data_vec.size(); } //获得优先队列头元素 ElemType top() { return data_vec.front(); } //添加元素 void push(const ElemType &t) { data_vec.push_back(t); push_heap(data_vec.begin(), data_vec.end()); } //弹出队首元素 void pop() { pop_heap(data_vec.begin(), data_vec.end()); data_vec.pop_back(); } }; template 
        
          priority_queue_
         
          ::priority_queue_(ElemType *data, const int n) { //拷贝数组data中的元素到vector中，并建立优先队列 for(int i=0; i
          
            void print(priority_queue_
           
             &pq) { while(!pq.empty())//也可以用 size() { cout<
            
              pq1;//默认构造函数 for(i=0; i
             
               pq2(arr, len); print(pq2); return 0; }

运行结果如下：

priority_queue的模板声明带有三个参数，priority_queue Type 为数据类型， Container 为保存数据的容器，Functional

为元素比较方式。其中 Container 必须是用数组实现的容器,比如 vectZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciwgZGVxdWUgtauyu8Tc08MgbGlzdKGjU1RMwO/D5sjdxvfErMjP08O1xMrHIHZlY3Rvci4gsci9z7e9yr3ErMjP08Mgb3BlcmF0b3I8ICw8L3A+CjxwPsv50tTI57n7xOOw0brzw+bBqbj2ss7K/SDIscqhtcS7sKOs08XPyLbTwdC+zcrHtPO2pbbRoaM8L3A+CjxwPsjnufvSqtPDtb3QobalttGjrNTy0ruw49KqsNHEo7DltcTI/bj2ss7K/ba8tPi9+MiloaNTVEzA78PmtqjS5cHL0ru49rfCuq/K/SBncmVhdGVyPFR5cGU+o6y21NPau/mxvsDg0M2/ydLU08PV4rj2t8K6r8r9yfnD99ChtqW20aGjPC9wPgo8cD7XotLio7o8YnI+CjwvcD4KPHA+19S2qNLlwODQzdbY1Nggb3BlcmF0b3I8ILrzo6zJ+cP3ttTP88qxvs2/ydLU1ru0+NK7uPbEo7Dlss7K/aGjtMvKsbK7xNzP8bv5sb7A4NDN1eLR+cn5w/dwcmlvcml0eV9xdWV1ZTxOb2RlLCB2ZWN0b3I8Tm9kZT4sIGdyZWF0ZXI8Tm9kZT4gPjs8L3A+CjxwPtSt0vLKxyBncmVhdGVyPE5vZGU+IMO709C2qNLlo6zI57n7z+vTw9Xi1ta3vbeotqjS5dTyv8nS1LC0yOfPwre9yr0ozca89tXi1ta3vcq9KaO6PGJyPgo8YnI+CjwvcD4KPHByZSBjbGFzcz0="brush:java;">// 自定义类型 typedef struct Node { int key; int data; .... }Node; //cmp的结构用于实现自定义的比较方法 struct cmp { bool operator()(Node a,Node b)//如果返回true，这两个元素就需要交换位置 { if(a.key==b.key) return a.data>b.data; return a.key>b.key; } };

优先队列实现霍夫曼编码

霍夫曼编码, 浩子大叔的blog也有讨论。

霍夫曼编码一般采用前缀编码 -- -- 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。

算法思想:

构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，

新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。其实这就是一个贪心策略，属于贪心算法的典型应用。

具体关于证明可以参考<算法导论>，里面证明比较详细。下面给出代码。

// http://blog.csdn.net/daniel_ustc/article/details/17613359
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int M = 6;// 待编码字符个数 typedef struct Tree { int freq;//出现频率,即 权值 char key;//字符 struct Tree *left, *right; Tree(int fr=0, char k='\0',Tree *l=nullptr, Tree *r=nullptr): freq(fr),key(k),left(l),right(r){}; }Tree,*pTree; // 自定义仿函数 struct cmp { bool operator() (Tree *a, Tree *b) { return a->freq>b->freq;//注意是> or < 不能用 - 和c中的qsort不同 } }; // 优先队列 priority_queue
      
       , cmp> pque; // 利用中序遍历的方法输出霍夫曼编码 //左0右1，迭代完一次st回退一个字符 void print_Code(Tree *proot, string st) { if(proot == NULL) return ; if(pro

C++ STL 优先队列 及其 霍夫曼编码应用示例(一)

优先队列(priority queue)

c++ priority_queue

优先队列实现霍夫曼编码

C++ STL 优先队列及其霍夫曼编码应用示例(一)