一个利用小顶堆构造哈夫曼树的C++算法  

AN ALGORITHM IN C++ FOR BUILDING HUFFMAN TREE WITH MIN-HEAP

作　　者：付勇[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830044

出　　处：《计算机应用与软件》2011年第3期253-256,共4页Computer Applications and Software

摘　　要：在研究了现有的一些算法的基础上,提出了一种新的构造哈夫曼树的C++算法。巧妙地运用了小顶堆的特点,以哈夫曼树的结点权值和结点指针组成的结构为小顶堆的数据元素,最初在小顶堆存放由叶子结点构成的若干个哈夫曼树的根结点的地址指针和作为关键值的权值,然后不断从小顶堆中取出一对权值最小的哈夫曼树的根结点指针,构造出这两个结点的双亲结点,并将双亲结点信息插入到小顶堆中。这种取出和插入的操作循环往复,直到构造出一棵独立的哈夫曼树为止。这一算法构思巧妙,简洁明快,具有很好的实际应用价值。This paper gives a new algorithm in C＋＋ for building Huffman tree based on investigating some of the existing algorithms.The algorithm skillfully employs the feature of min-heap,uses the structure composed of node＇s weight and node＇s pointer of Huffman tree as the data elements of min-heap,and stores in min-heap initially some address pointers of root nodes of Huffman tree and the weight which is the key value,both are structured by the leaf nodes,then constantly picks up a pair of pointers of the root node of Huffman tree with least weight from the min-heap to make their parent node and inserts the information of the parent node into the min-heap.The picking up and insertion are the cyclic operation,until a single Huffman tree has been built.It is an ingeniously conceived algorithm with concision and lucidity,and has good practical value of application.

关 键 词：小顶堆 哈夫曼树 算法 C++ 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]