贪心算法——Huffman编码（哈夫曼编码） 收藏

注：实现Huffman编码是用贪心算法来实现的，证明Huffman的贪心选择和最优子结构很麻烦，我没有看懂（算法导论.中文版P234），这里只是给出了实现Huffman编码的实现代码。实现Huffman最好的数据结构时优先级队列（可以通过最小堆来实现）。整个算法的时间复杂度可以达到nlg(n)，这里为了简单，没有实现最小堆，而使用的是STL中的set，通过实现正确的比较函数对象，每次可以取得优先级（字符出现频度最低）最大的值。但是这里的时间复杂度却提高了，因为操作set的选择时，时间复杂度时lgn,但是随着选择的，选择“未被访问的最高优先级的两个元素（flag=0）”的探测次数也为增大，平均探测次数是n/2，因此最后实现Huffman的时间复杂度将是n^2lg(n)。当然也可以通过记录每次选择元素时其在set中的位置（偏移量），下次选择时直接通过这个偏移量找到合适位置，探测的时间复杂度将会是1，最后实现Huffman的时间复杂度也可以达到nlog(n)。

n^2lg(n)的实现代码如下：

view plaincopy to clipboardprint?
#include <iostream>
#include <set>
using namespace std;
struct Node
{
int fu;//字符出现频度
int flag;//访问标识
struct Node *lc;//左孩子
struct Node *rc;//右孩子
};
struct compare_node//Node放在set<Node*>中的比较函数对象
{
bool operator()(const Node* node1,const Node *node2)const
{
return node1->fu < node2->fu;
}
};
set < Node *,compare_node> queue;
const int N = 6;
int s[N];//保存字符的编码
int f[N];//频度
struct Node *huffman()
{
int i = 0;
while(i<N-1)//一共需要N-1次合并操作（由叶子节点合并成具有左右孩子的非叶子节点）
{
Node *child[2];//找到两个出现频度最小的值
set< Node *,compare_node>::iterator it = queue.begin();
int lr = 0;
while(it!=queue.end() && lr <2)
{
if((*it)->flag ==0)//没有被访问过
{
child[lr] =*it;
(*it)->flag = 1;
lr ++;
}
it++;
}
Node *parent = new Node;

parent->flag = 0;
parent->lc = child[0];
parent->rc = child[1];
parent->fu = child[0]->fu + child[1]->fu;
queue.insert(parent);
i++;

}
int count = queue.size();
set <Node*>::reverse_iterator rit = queue.rbegin();
if(rit!=queue.rend())
return *rit;
else
return NULL;
}
//打印每个字符（频度值）的编码
void print(Node * root,int c)
{
if(root == NULL)
return;
else
{
if( root->lc != NULL)
{
s[c++] = 0;
print(root->lc,c);
}
if(root->rc!=NULL)
{
c--;
s[c++]=1;
print(root->rc,c);
}
//输出字符的编码
if(root->lc == NULL && root->rc == NULL)
{
cout << root->fu <<" ";
int i =0;
for(i=0;i<c;i++)
cout << s[i];
cout << endl;
}
}
}
int main()
{
int i =0;
Node *p = NULL;
for(i=0;i<N;i++)
{
cin>>f[i];
p = new Node;
p->flag = 0;
p->fu = f[i];
p->lc = NULL;
p->rc = NULL;
queue.insert(p);
}
Node *node = huffman();
print(node,0);
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/08/19/4464514.aspx