用C++ std::priority_queue 实现哈夫曼算法我想每个计算机专业的学生或多或少都接触过哈夫曼编码，数据结构中的老问题了。大体就是给出一些字符，和这些字符的出现频率，让你为这些字符设计一个二进制编码，要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树（二叉树），其基本思路是，每次从这些字符中挑出两个频率最低的，然后构造一个新的结点，使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了，我就不多说了。主要讲下这次我用C++实现时遇到的问题。首先，我定义了一个哈夫曼树结点：
class hNode
{
public:
friend bool operator > (hNode n1,hNode n2); //定义了大于符号，供优先队列排列使用
hNode(string d="",int i=0,hNode* l = NULL,hNode* r =NULL):left(l),right(r),data(d),value(i){}
hNode* left;
hNode* right;
string data; //储存的字符串
int value; //字符串出现的次数
};
bool operator >(hNode n1,hNode n2)
{
return n1.value > n2.value;
}
因为只是算法课的小作业，所以我也不准备为hNode定义完整的二叉树操作，仅仅只是存放数据的对象，所以只有一个构造函数，并且所有的data member都是公有的。
这此写这个算法会遇到大麻烦，主要因为是用了std::priority_queue容器。当时考虑到在哈夫曼中要每次挑选两个频率最小（即出现次数最小，我那个hNode里的value是出现的次数），很自然的就想到了std::priority_queue容器，优先队列每次都会弹出队列中权值最高的元素，这个特性无疑是实现哈夫曼算法的最佳选择。然而因为第一次用std::priority_queue容器，结果出了不少问题，好在最后都一一解决，也学到了不少东西。
初步的设想是这样的，先把所有的hNode对象都压入优先队列中去，然后每次弹出两个，组成一个新的结点，再把新的结点压入队列，重复这一步骤，当队列中只有一个元素时，哈夫曼树也就完成了。像这样：（是错的，可别学）
while(...)
{
std::priority_queue<hNode> q;
.....
hNode h1 = q.top();
q.pop();
hNode h2 = q.top();
q.pop();
hNode r;
r.left = h1;
r.right = h2;
r.value = h1.value + h2.value;
q.push(r);
}
然而遭遇的第一个问题是，STL的所有容器的的插入都是基于by value语义的，也就是要生成一个对象的副本放在容器中。这样的后果就是hNode的left,right指针都指到不知道什么地方去了。大家可以稍微画几个图试一下，就知道出了什么问题了。考虑一下后，发现如果队列里存放hNode的指针，就不会出现这个问题了，于是改写成：
然而马上遭遇了第二个问题。std::priority_queue在判断优先关系的时候，直接比较指针的地址，而不是指针指向的对象的大小关系。而指针不是类，我没办法重写指针的比较操作。程序陷入了困境之中。std::priority_queue默认使用Greater<>模板来生成一个function object来对元素进行比较，我试图为Greater<>写一个hNode*的特化版本来改变优先队列对hNode*的比较，然而也没有成功。山重水复疑无路之时，突然想到为什么不直接为优先队列写一个function object来替代Greater<>不就可以了吗？赶快写下如下代码：
struct phNodeComp
{
bool operator () (const hNode*& left,const hNode*& right) const
{
return left->value > right->value;
}
};
然后把std::priority_queue的申明变为：
priority_queue<hNode*,vector<hNode*>,phNodeComp > pq;
终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的，一定要自己实践了才会有真正的认识。
posted on 2004-03-19 19:47 Justin Shen 评论(6) 编辑 收藏
Comments
# re: 用C++ std::priority_queue 实现哈夫曼算法
earthharp
只有成树
没有编码解码吗？
我觉得用BucketSort还要优秀一些
注意你的空间是否正确回收
Posted @ 2004-03-20 01:06
# re: 用C++ std::priority_queue 实现哈夫曼算法
Justin Shen
目前只做到把每个字符的编码打印出来，因为老师只要求到这点，实际做哈夫曼编码还是会有一点问题。空间回收在遍历哈夫曼树的过程中一起完成了。
vector<
int> v;
void DoPrint(hNode* r)
{
if (r->left ==NULL && r->right == NULL)
{
cout << r->data <<": ";
for (int i = 0;i<v.size();++i)
cout << v;
cout << endl;
v.pop_back();
delete r;
return ;
}
if (r->left)
{
v.push_back(0);
DoPrint(r->left);
}
if (r->right)
{
v.push_back(1);
DoPrint(r->right);
}
v.pop_back();
}
class hNode
{
public:
friend bool operator > (hNode n1,hNode n2); //定义了大于符号，供优先队列排列使用
hNode(string d="",int i=0,hNode* l = NULL,hNode* r =NULL):left(l),right(r),data(d),value(i){}
hNode* left;
hNode* right;
string data; //储存的字符串
int value; //字符串出现的次数
};
bool operator >(hNode n1,hNode n2)
{
return n1.value > n2.value;
}
因为只是算法课的小作业，所以我也不准备为hNode定义完整的二叉树操作，仅仅只是存放数据的对象，所以只有一个构造函数，并且所有的data member都是公有的。
这此写这个算法会遇到大麻烦，主要因为是用了std::priority_queue容器。当时考虑到在哈夫曼中要每次挑选两个频率最小（即出现次数最小，我那个hNode里的value是出现的次数），很自然的就想到了std::priority_queue容器，优先队列每次都会弹出队列中权值最高的元素，这个特性无疑是实现哈夫曼算法的最佳选择。然而因为第一次用std::priority_queue容器，结果出了不少问题，好在最后都一一解决，也学到了不少东西。
初步的设想是这样的，先把所有的hNode对象都压入优先队列中去，然后每次弹出两个，组成一个新的结点，再把新的结点压入队列，重复这一步骤，当队列中只有一个元素时，哈夫曼树也就完成了。像这样：（是错的，可别学）
while(...)
{
std::priority_queue<hNode> q;
.....
hNode h1 = q.top();
q.pop();
hNode h2 = q.top();
q.pop();
hNode r;
r.left = h1;
r.right = h2;
r.value = h1.value + h2.value;
q.push(r);
}
然而遭遇的第一个问题是，STL的所有容器的的插入都是基于by value语义的，也就是要生成一个对象的副本放在容器中。这样的后果就是hNode的left,right指针都指到不知道什么地方去了。大家可以稍微画几个图试一下，就知道出了什么问题了。考虑一下后，发现如果队列里存放hNode的指针，就不会出现这个问题了，于是改写成：
然而马上遭遇了第二个问题。std::priority_queue在判断优先关系的时候，直接比较指针的地址，而不是指针指向的对象的大小关系。而指针不是类，我没办法重写指针的比较操作。程序陷入了困境之中。std::priority_queue默认使用Greater<>模板来生成一个function object来对元素进行比较，我试图为Greater<>写一个hNode*的特化版本来改变优先队列对hNode*的比较，然而也没有成功。山重水复疑无路之时，突然想到为什么不直接为优先队列写一个function object来替代Greater<>不就可以了吗？赶快写下如下代码：
struct phNodeComp
{ bool operator () (const hNode*& left,const hNode*& right) const { return left->value > right->value; } };
然后把std::priority_queue的申明变为：
priority_queue<hNode*,vector<hNode*>,phNodeComp > pq;
终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的，一定要自己实践了才会有真正的认识。
posted on 2004-03-19 19:47 Justin Shen 评论(6) 编辑 收藏
Comments
# re: 用C++ std::priority_queue 实现哈夫曼算法
earthharp
只有成树
没有编码解码吗？
我觉得用BucketSort还要优秀一些
注意你的空间是否正确回收
Posted @ 2004-03-20 01:06
# re: 用C++ std::priority_queue 实现哈夫曼算法
Justin Shen
目前只做到把每个字符的编码打印出来，因为老师只要求到这点，实际做哈夫曼编码还是会有一点问题。空间回收在遍历哈夫曼树的过程中一起完成了。
vector<
int> v;
void DoPrint(hNode* r)
{ if (r->left ==NULL && r->right == NULL) { cout << r->data <<": "; for (int i = 0;i<v.size();++i) cout << v; cout << endl; v.pop_back(); delete r; return ; } if (r->left) { v.push_back(0); DoPrint(r->left); } if (r->right) { v.push_back(1); DoPrint(r->right); } v.pop_back(); }
