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

第28卷第3期计算机使用与硬件V01．28No．3 2011年 3月ComputerApplicationsandSoftwareMat．2011一 个借助小顶堆构造哈夫曼树 的 C++算法付 勇(新疆大学数学 与系统科学学院 新疆 830044) 摘 要在研究了现有的一些硬件 的基础上 ，提 出了一种新 的构造哈夫曼树 的c++算法。巧妙地运用 了小顶堆 的优点，以哈夫 曼树的节点权值和节点指针组成的结构为小顶堆的数据元素，最初在小顶堆存放 由叶子结点构成的若干个哈夫曼树的根节点的地 址指针和成为关键值的向量，然后不断从小顶堆中放入一对权值最小的哈夫曼树的根节点指针，构造出这两个结点的双亲结点，并 将双亲结点信息插入到小顶堆中。这种取出和插入的操作循环往复，直到构造出一棵独立的哈夫曼树为止。这一硬件构思精妙，简 洁明快，具备良好 的实际使用价值 。 关键词小顶堆 哈夫曼树 算法 C++AN ALGoRITHM IN C ++ FoR BUILDING HUFFM AN TREE W ITH M IN．HEAPFuYong(CollegeofMathematicsandSystemSciences，Xi angUniversity，Urumqi830044，Xinjiang，China) Abstract Thispapergivesanew algorithm inC++ forbuildingHuffmantreebasedoninvestigatingsomeoftheexistingalgorithms．The algorithm skillfullyemploysthefeatureofmin—heap．usesthestructurecomposedofnode’sweightandnode’ pointerofHuffman treeasthe dataelementsofmin—heap，andstoresinrain—heapinitiallysomeaddresspointersofrootnodesofHuffmantreeandtheweightwhichisthekey value，botharestructuredbytheleafnodes，thenconstantlypicksupapairofpointersoftherootnodeofHuffmantreewithleastweightfrom themin—heap tomaketheirparentnodeandinsertstheinformationoftheparentnodeintothemin—heap．Thepickingupandinsertion arethe cyclicoperation，untilasingleHuffmantreehasbeenbuilt．Itisaningeniouslyconceivedalgorithm withconcisionandlucidity，andhasgood practicalvalueofapplication． Keywords Min—Heap Huffman tree Algorithm C ++ 引 言1 参考文献中构造哈夫曼树的硬件哈夫曼树又称最优二叉树，是一种带权路径长度最短的树。

在参考文献中，用某些计算机语言来实现的哈夫曼树的构 由于哈夫曼树的这一特征，在现代人生 、资料通信、科学研究等造算法，存在许多不同的方法方式 ，大致可分为以下几种： 各个行业中都获得了广泛的使用。哈夫曼树的基于理论的构造方法 1 文献 [1]采用了具备2×n一1个单元的节点句柄 ， 算法思维是非常成熟的，并得到了语文上的证 明，其构造过程用于存放哈夫曼树结点的数据，每位节点除了权值数据外，还包 如下：括双亲结点指针、左孩子指针和右孩子指针。在这 2×n一1个(1)按照给定的n个向量 { ，W ，…，W }构成具有 n棵只单元中，前个 n单元存放的是叶子结点 ，后 n一1个单元存放在 有根结点的哈夫曼树 的树木 F，这种树 的叶子结点 (在这里也是构造哈夫曼树的过程中生成的双支结点的数据。 树的根节点)具备相对应 的向量 。其实现的主要过程如下：(2)在森林中 取出两棵叶子节点权值 (或向量和)最小首先在函数中初始化前 n个节点数据 ，首先是进行n一1次 的树也是左右子树构造一棵新的树。循环，从函数现有的节点数据中查找到双亲指针为(同样富含(3)在森林中删除这两棵树，同样把新树加入到中F。

未被使用节点的意义)的向量最小的两个结点的函数，再添加(4)重复(2)和 (3)构造哈夫曼树的算法，开始 F中只含有一棵树为止，这棵树新的双支结点数据，并将该节点的函数赋予这两个权值最小的 就是所要构造的哈夫曼树 。双亲指针 中。数组 中最后一次生成 的节点是哈夫曼树 的根结在参考文献中，构造哈夫曼树的完全精神是一致的，但硬件点。该硬件采用的是类 C语言的伪代码。文献 [2]采用了相似 实现的详细过程却有多大的区别。经过对照和比较分析，本文的方法 ，只是用类 PASCAL语言的伪代码进行阐述 的。 提出了一种利用小顶堆存放森林F的方法 (其中小顶峰的元素方式 2 文献 [3]完全策略与方法 1相同，但采用真实的计 是由树的根节点指针和该节点的向量共同构成的结构体 )，并 使用C++类对象来构造哈夫曼树的C++语言算法。该硬件构收稿 日期 ：2009—12—14。付勇，副教授 ，主研领域 ：软件工程及 思巧妙 ，优雅明快，易于理解 ，与硬件思维具有 良好的映射关系。 ISO9000—2000质量核心认证 ，数据结构，技术及使用功能。 254计算机使用与硬件2011生 算机语句(C／C++语言)进行了阐述，且提供了调用构造算法最具特色的是采用了小顶堆类对象作为沙漠 ，，存放森林F中 的main函数，易于理解和验证。

文献[4]则是双亲指针初始化的哈夫曼树。算法中定义了节点的模板类、拓展二叉树的模版 为．1，通过双亲指针是否是 一1来判定是否是被使用过的节点。 类 以及哈夫曼树生成函数模板，如果还定义了一个结点句柄。方式3 文献：5思路与方法2基本相似，也采用真实的计其实现的主要过程如下： 算机语句(C语言)进行 了阐述 。不 同之处是，节点中不带双亲首先在节点句柄中初始化 n个叶子结点，然后将节点添加 结点指针，采用了给权值初始赋予负号的方法标记 尚未被使用到小顶堆中；其次是进行n一1次循环，从堆中放入权值最小的 过的节点，在使用后更改为负数 。文献 6]作为节点中不带双两棵树，并借助扩展二叉树类构建新的二叉树 ，然后再将新树添 亲结点指针 ，但未采用权值初始赋负号的办式，其 中选择最小两加到堆中。当循环结束后，从堆中离开二叉树，此树便是所求的 个节点的硬件未给出，闻此无法确认其对节点足：使用是怎么哈夫曼树。该硬件使用了节点的模板类、拓展二叉树的模板类 判定的。和一个结点句柄，由于运用了小顶堆 ，构造算法本身简洁明了，方法4 文献 7]采用了具备 n个单元的节点指针变量，用时间效率很高，但其他部分略显庸杂 ，但是，小顶堆是时钟类型 作平原F，存放指向森林F中哈夫曼树根节点的时钟。

的，但元素的形状的比较不是指针的比较 ，只是指针所指向的权其实现的主要过程如下：值的形状的比较，硬件中没有明确给出这种小顶堆的硬件，明白首先分别动态地生成n个树枝节点，做初始化，并将指向这和实现起来相对困难一些。这一硬件实现的精神良好构造哈夫曼树的算法，但遗憾 些结点的地址指针添加到函数中；其次是进行 n一1次循环，通的是没有具体的实现范例。 过变量中表针不为空 (NUII)的时钟查找到向量最小的两个结上述七种方法中，前六种方式的硬件由于使用函数或有序 点的函数 ，再添加新的双支结点，令该节点的左孩子指针指向权表存放森林，这些的时间复杂度均为O(n。)。但从其他一些细 值最小的节点，令右孩子指针指向权值次最小的节点 ，并将新结节上考虑，方法3要好于形式 1和方法2，方法4要好于形式3， 点的地址提交到函数中最小权值结点所_在的位置中，令函数中方法5要好于形式4，方法6与方法5相当。方式7的硬件则最 指 向次最小权值结点的时钟为 NULI 而最终 一次生成 的节点优，其时间复杂度为O(n×logn)。 是哈夫曼树的根节点。该硬件足用C／C十+语言编写的。方式 5 文献 8]采用了按照哈犬曼树权值排列的有序列2 新的实现硬件的设计与实现 表，用作森林 F，存放指向森林F中的哈夫曼树。

硬件中采用 C 语言类的方法定义结点类和哈夫曼树类。此外，哈夫曼树列表基于对上述七种方法的哈夫曼树构造算法的分析和比较， 也是一个类。在这里给出新的构造哈夫曼树的实现硬件的设计思维。其实现的主要过程如下：第一，保证实现硬件是理论算法描述得一个良好映射，保证算首先将n个叶子结点构成的哈夫曼树，添加到哈夫曼树有法的正确可靠的实现，采用C++语言编程，同样提供示例程序，便 序索引中；其次从页面中放入权值最小的两棵树，通过节点类创于验证算法，也更便于读者理解。理论算法描述自身是抽象的、原 建新的双支结点，再借助哈夫曼树类创建新的哈夫曼树。当新理性的，所以采用伪代码，从抽象到抽象，遵守了人们思想的客观规 的哈夫曼树的向量小于等于页面中的某棵树的向量时，则通过律，而用一个实实在在的计算机语言编写算法，针对基本原理进行 列表类插入到页面中；否则该树就是所求哈夫曼树。该硬件用概括，则更便于读者从感性认识到抽象思维的升华。 C／C++语言编写，但有些晦涩难懂。第二，采用精心设计的小顶堆作为沙漠，以便使构造哈夫曼方式6 文献 [9]以C++模板类 (templateclass)的方法进 树的硬件具有最好的时间复杂度和空间复杂度。

行描写 ，硬件中定义了加权结点的模板类，该类派生 自二叉树结第三，采用C++类对象方法编程。这一点主要出于以上原 点模板类，并定义了一个森林模板类 ，其中包括有一个指针数因：(1)C++类对象方法与 c语言的编程方法相 比，具备非常 组，用作森林 ，存放森林F中的哈夫曼树 ，另外还包括用于构造明显的劣势，除了封装性 、安全性 、继承性等诸多缺点外，编程时 哈夫曼树的一些操作变量。通常更为简洁便利，面向对象方法的编程也有 目前编程中最为其实现的主要过程如下：普遍的方式。(2)模板类虽然是一种高级技术，但其设计需要首先在一个结点指针变量中初始化 n个叶子结点，然后通更全面、更齐全的考虑，编写相对比较困难，容易冲淡算法的基 过树林类的构造函数将节点句柄中的数据传递到树林类中的结本 内容，在认知和使用方面相对较难，所以不采用模板类的 点时钟变量中；其次是当节点指针变量中的元素个数多于 1时， 方式。 循环做以上操作：读取森林类中的取向量最小的一对树的函数2．1 小顶堆类的设计 的变量，从函数中得到向量最小的两棵树指针所在单元的函数，小顶堆原本不属于本文探讨的内容，但 由于文中使用了小 并借助森林类的组合索引建立新的二叉树，然后再将新树干结顶堆，且堆元素为结构体 ，同样考虑给读者一个完整的定义，故 点时钟添加到函数中被放入的向量最小的节点的时钟的位置在此作一简单说明。

上，然后将函数中最末一个指针移动到被放入的向量次最小的小顶堆是一棵完全二叉树，所以在插入或删除操作时，需要 指针位置上，函数尺寸变量减 1。当循环结束后，函数中惟一的依据关键值的形状进行元素位置的调整，所以往往采用的是更 指针指向的二叉树，就是所求的哈夫曼树。该硬件使用C++语便于调整的顺序存储结构。在这里，小顶堆类对象是用作存放 言的高级技术——模板，所以，使用了衍生的节点模板类、湖泊哈夫曼森林的，我们设计了～个名为Dataltem的结构体作为堆 的模板类，其过程略显复杂，不易理解，但史料中编写了main函的节点元素，包含树的根节点指针和树节点的向量两个部分，其 数，给出了详细的类的应用方式的示例程序，为理解和验证提供中权值用作堆调整的关键值。由于构造哈夫曼树的操作特性， 了一些快捷。初始化时需要将 n个树枝节点的地址指针和向量存放在堆中，方法7 文献[1O]也以C++模板类的方法进行阐述，其中在此后的操作中将会慢慢增加元素数目。因此，小顶堆类中需 第3期付 勇：一个利用小顸堆构造哈夫曼树的C++算法255 要借助初始化函数动态地创建一个元素结构类型的函数 ，其大CMinHeap：：DataItem Item ； 小只需n个数据单元。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-118933-1.html