PHP数据结构（八）——赫夫曼树实现字符串编解码(理论) （原创内容，转载请注明来源，谢谢） 一、树和森林 1、树的三种存储结构 1)双亲表示法——数组下标、值、上一级数组下标（根节点下标为负一） 2)孩子表示法 方法一：孩子链表——数组下标、值、下一级数组链表（无下一级指向null） 方法二：带父节点的子链表——结合双亲表示法和孩子链表，包含数组下标、值、上一级数组下标（根节点下标为负一）、下一级数组链表（无下一级指向null）。 3)孩子兄弟表示法——又称二叉树表示法或二叉链表表示法，
PHP数据结构（八）——赫夫曼树实现字符串编解码(实践2) （原创内容，转载请注明来源，谢谢） 公众号规定不能超过3000字，只能分两篇，见谅。 由于需要分两篇来讲，本篇接上篇的内容，假定已经获取到编
PHP数据结构（八）——赫夫曼树实现字符串编解码(实践1) （原创内容，转载请注明来源，谢谢） 公众号规定不能超过3000字，只能分两篇，见谅。 由于需要分两篇来讲，本篇主要讲解编码的
PHP数据结构（二十五）——并归排序 （原创内容，转载请注明来源，谢谢） 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进行排序的方式如下： 假设初始序列含有n个记录，则看成是n个有序的子序列，每个子序列长度是1，然后两两合并，得到n/2个长度为2或者1（元素总数是奇数时，最后一个元素是单个的）的子序列。然后再进行归并，直至归并成一个数组。此方法也成为2-路并归排序。 二、算法 并归排序有两个核心——拆分、合并。 1）对于拆分，需要把数组拆成仅含一
PHP数据结构（十八）——直接插入排序 （原创内容，转载请注明来源，谢谢） 一、概述 插入排序分为直接插入排序、其他插入排序、希尔排序。其他插入排序又分为折半插入排序、2-路插入排序。 二、直接插入排序 直接插入排序是一种最简单的排序方法，时间复杂度O(n2)，实现方式是将一个记录插入到已经排序好的有序表，得到一个新的、记录数增加1的有序表。 插入排序的核心思想，即假设原数组的第0位至第i-1位都是有序排列的（如从小到大），当第i位出现顺序错误（如第i位的值小于第i-1位），则需要进行插入排序。 1、
在了解赫夫曼编码之前，我们必须了解一下赫夫曼树，赫夫曼编码就是基于赫夫曼树实现的。
给定n个权值作为n个叶子节点，构造一课二叉树，若该树的带权路径长度和（wpl）达到最小，称这样的二叉树为最优二叉树，也就是赫夫曼树。
PHP数据结构（二十一）——希尔排序 （原创内容，转载请注明来源，谢谢） 一、概述 希尔排序，又称缩小增量排序，也属于插入排序类方法，时间上有较大改进。前面叙述的插入排序方法的时间复杂度都是O(n2)，当待排序记录都是正序时，时间复杂度提高到O(n)。 希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体进行一次插入排序。 二、算法 希尔排序实质上就是跳跃版的直接插入排序，其每次都设定一个不同的增量，如第一次增量是5、第二次增量是3
首先，赫夫曼编码是一种变长编码方式，其目标是使得编码的总长度最短。赫夫曼编码的生成基于赫夫曼树，其中树的每个内部节点表示两个子节点频率的和，而叶子节点则代表原始字符及其频率。在构建赫夫曼树时，我们每次选择频率最低的两个节点来生成一个新的父节点，直到只剩下一个节点（即根节点）为止。
PHP数据结构（十二）——静态查找表 （原创内容，转载请注明来源，谢谢） 一、概念 1、查找表：由同一类型数据元素构成的集合。 2、静态查找表：只进行查找（包括确认元素是否存在、查找元素的值），不进行增加和删除操作。 3、动态查找表：与静态查找表相对应，除了查找，还会进行插入与删除操作。 4、关键字：用于标识一个数据元素，如果对应的数据元素唯一，则为主关键字。如果若干个关键字可以唯一确定一个数据元素，称这些关键字为次关键字。
4.带权路径的长度：树中所有的叶子节点的权值乘其到根节点的路径长度与最终的赫夫曼编码长度成正比关系。
这种情况，权值为 2 * 13 + 2 * 7 + 2 * 8 + 2 * 3 = 62。
PHP数据结构（十三） ——动态查找表（二叉排序树） （原创内容，转载请注明来源，谢谢） 一、概念 1、动态查找表特点 当对动态查找表进行查找时，如果查找成功，会返回查找结果；如果查找失败，会对动态查找表插入查找结果，并且根据各类动态查找表的性质，对表进行动态调整。 2、二叉排序树（又称二叉查找树） 二叉排序树或者是一棵空树，或者满足以下特性： 1）若左子树非空，则左子树的所有节点小于根节点； 2）若右子树非空，则右子树的所有节点大
PHP数据结构（十）——有向无环图与拓扑算法 （原创内容，转载请注明来源，谢谢） 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。如下图所示。 二、、拓扑排序 拓扑排序
推广赫夫曼算法以生成三进制码字需要对算法进行一定的修改，确保在每一步选择频率最低的三个节点进行合并，并生成对应的三进制码。以下是推广赫夫曼算法的Go语言实现，并附带证明其能生成最优三进制码的思路。
大顶堆特点：arr[i]>=arr[2i+1]&&arr[i]>=arr[2+2]
参考资料 《算法（java）》 — — Robert Sedgewick， Kevin Wayne 《数据结构》 — — 严蔚敏 赫夫曼树的概念 要了解赫夫曼树，我们要首先从扩充二叉树说起 二叉树结点的度 结点的度指的是二叉树结点的分支数目， 如果某个结点没有孩子结点，即没有分支，那么它的度是0；如果有一个孩子结点， 那么它的度数是1；如果既有左孩子也有右孩子， 那么这个结点的度是2. 扩充
PHP数据结构（十七）——内部排序综述 （原创内容，转载请注明来源，谢谢） 一、稳定性 假设Ki=Kj(1<=i,j<=n,i!=j)，且排在序列前的序列中Ri领先于Rj（即i>j）。 1）若在排序后的序列中，Ri必然仍领先于Rj，则称所用的排序方法是稳定的。 2）如果Ri可能出现在Rj之后的情况，则称所用的排序方法是不稳定的。 用一句话描述，就是原数组中两个相同的数字，一个在前一个在后，经过某种排序后（无论重新使用该方法排序多少次），仍一个在前一个在后，则称为稳定。
给定N个权值作为N个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也成为哈夫曼树（huffman-tree），还有的树翻译为霍夫曼树。
给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.
PHP数据结构（十四） ——键树（双链树） （原创内容，转载请注明来源，谢谢） 一、概念 键树又称为数字查找树，该树的度>=2，每个节点不是存储关键字，而是存储组成关键字的一个字符或数值的一个数字。
PHP数据结构（十五）——哈希表 （原创内容，转载请注明来源，谢谢） 一、概述 查找的效率与查找的次数有关，查找的次数越少速度越快。因此，希望能够一次查找出结果，此时键值一一对应，称满足这条件的f(k)为哈希函数。 1、定义 1）冲突 不同的关键字通过哈希函数，得到同一个地址，称为冲突。具有相同函数值的关键字称为同义词。 2）哈希表 根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映像到一个有限连续的地址集上，以关键字的“像”作为记录的位置，此表称为哈希
看完了这么多树，来看个二叉树的小应用——赫夫曼编码（Huffman Coding），是一种用于无损数据压缩的熵编码（权编码）算法。由大卫·霍夫曼在1952年发明（这居然只是他1951年的期末作业而已，1952年发表为论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）https://web.archive.org/web/20050530145744/http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf）。它又称最优二叉树，是一种带权路径长度最短的二叉树。是二叉树的一个常见应用。
PHP数据结构（二十二）——快速排序 （原创内容，转载请注明来源，谢谢） 一、概述 前面的插入排序，都是以移动的方式进行排序。快速排序，则是以交换的方式进行排序。 二、冒泡排序 提到交换的方式进行排序，首先可以提到冒泡排序。 1、算法 冒泡排序是逐个进行比较再进行交换的排序方式，假设是以从小到大的顺序排列。 1）先用第一个数和第二个数比较，如果第一个数比较大，则和第二个数进行互换，否则两个数保持不变。 2）再用第二个数与第三个数比较，直至第n-1个数与第n个数进行比较。这称为一轮的冒
PHP数据结构（十一）——图的连通性问题与最小生成树算法（2） （原创内容，转载请注明来源，谢谢） 再次遇到微信公众号限制字数3000字的问题。因此将Kruskal算法放于本文中进行描述。本文接上一篇文章。 4、Kruskal算法 1）该算法的时间复杂度为O(eloge)，e表示边的数目，即该算法的时间复杂度和顶点数目无关。该算法适用于边数较少的稀疏网。 2）算法内容 假设N={V, {E}}是连通网，算法初始状态为包含图中的所有的点，没有边的T=(V, {
之前说到了如何构建赫夫曼树，那么赫夫曼树有什么用呢？赫夫曼树经典的应用之一就是赫夫曼编码。
PHP数据结构（二十三）——选择排序 （原创内容，转载请注明来源，谢谢） 一、概述 选择排序的基本思想，是每一趟在n-i+1（i=1,2…n-1）个记录中选取关键字最小的记录作为第i个记录。选择排序分为简单选择排序、树形选择排序、堆排序。 二、简单选择排序 简单选择排序，即完全按照上述的说法进行排序。时间复杂度O(n2)。由于比较简单，不具体描述。 1、算法 1）遍历整个数组，找到最小值放置于第一个位置。 2）遍历从第二个位置至末尾的数组，找到最小值放在第二个位置。
PHP数据结构（十六）——B树 （原创内容，转载请注明来源，谢谢） 一、概述 B树在很多地方被称为“B-树”，因为B树的原英文名称为B-tree，很多人把其译作B-树，但是它的正确读法是B树，因此下面都用B树来表示B-tree。B树是一种多路平衡查找树，其对于加快查找速度具有重要意义。 1、定义 一棵m阶的B树（不是指m叉树，m是这棵树的度，下同），或者是空树，或者是满足下列特性的m叉树： 1）树中每个节点至多m个子树，m-1个关键字。 2）根节点若不
第六章 树 6.2 树的定义 树（Tree）的n个结点的有限集。当n=0时，称为空树。 任意一个非空树中： 1）有且仅有一个特定的称为根（root）的结点 2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2 …… 、Tm。其中每个集合本身又是一棵树，并且称为根的子树（SubTree）。 注意： 1）n>0时根节点的唯一的，不可能存在多个根节点。 2）m>0时，字数的个数没有限制，但是它们一定是互不相交的。 6.2.1 结点分类 结点拥有的子树个数称为结点的度（Degree）。 度为0的结
PHP数据结构（十九）——B+树 （原创内容，转载请注明来源，谢谢） 一、概述 B+树是B树的变种，在数据库系统、文件系统等方面，B+树的运用非常广泛。 1、B+树的要求 1）有n棵子树的结点中含有n个关键字。（B树是n-1个关键字。） 2）所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。这点意味着，叶子节点存在指向相邻叶子节点的指针。这个是在树形的数据结构中非常特殊的地方，使得B+
PHP数据结构（二十四）——堆排序 （原创内容，转载请注明来源，谢谢） 一、定义 堆排序也属于一种选择排序，效率较高且空间占用相对较少。 堆的定义：n个元素的序列(k1,k2…kn)，当且仅当满足以下1或者2的其中一种关系时，称为堆。 1）大顶堆：ki<=k2i且，ki<=k2i+1，其中i=1,2…n/2 2）小顶堆：ki>=k2i且，ki>=k2i+1，其中i=1,2…n/2 可将堆对应的一维数组看成一个完全二叉树，且满足非终端节点对应的值不大于（或不小于）其
①、给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树（Huffman Tree）、赫夫曼树、霍夫曼树。 ②、哈夫曼树是带权路径长度最短的树，权值较大的节点离根较近
PHP数据结构（十一）——图的连通性问题与最小生成树算法（1） （原创内容，转载请注明来源，谢谢） 一、连通分量和生成树 1、无向图 设E(G)为连通图G的所有边的集合，从图的任意一点出发遍历图，可以将E(G)分为T(G)和B(G)，T表示已经遍历过的边的集合，B表示剩余边的集合。因此，T与图G的所有顶点构成的极小连通子图，就是G的一棵生成树。由深度优先搜索的称为深度优先生成树；由广度优先搜索的称为广度优先生成树。 2、有向图 有向图和无向图类似。有向图的强连通分量，是对图进行深度优先遍历，遍历完成后，
给定N个数值作为N个叶子结点的权值，构造一颗二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也叫哈夫曼树。
顺序存储的特点是各个存储单位在逻辑和物理内存上都是相邻的,典型的就是代表就是数组,物理地址相邻因此我们可以通过下标很快的检索出一个元素
赫夫曼树应用场景 赫夫曼编码式赫夫曼树在电讯通信中的经典应用之一。 赫夫曼树也广泛的应用于数据文件的压缩。其压缩效率通常在 20% -90% 之间 生成赫夫曼编码 步骤与赫夫曼树类似 package xmht.datastructuresandalgorithms.datastructure.tree.huffmancode; import org.jetbrains.annotations.NotNull; import java.util.*; /** * @author shengjk1 *
PHP数据结构（二十）——其他插入排序 （原创内容，转载请注明来源，谢谢） 注：本文是衔接直接插入排序的，因此直接插入排序的相关内容请点击——PHP数据结构（十八） ——直接插入排序。 一、概述 当数据量n较小时，直接插入排序是一个很好的方法。但是，当n较大时，采用直接插入排序，速度较慢，效果不好。其他插入排序主要是指折半插入排序、2-路插入排序、表插入排序，两者在直接插入排序的基础上，减少比较和移动的次数，以达到加快速度。 二、折半插入排序 直接插入排序中，当需要查找第i个值应该放于哪个位
PHP数据结构（九）——图的定义、存储与两种方式遍历 （原创内容，转载请注明来源，谢谢） 一、定义和术语 1、不同于线性结构和树，图是任意两个元素之间都可以有关联的数据结构。 2、顶点：数据元素；弧：顶点A至顶点B的连线，弧是单向的，出发的点称为弧尾，抵达的点称为弧头；边：顶点A和B之间的连线，没有方向性。 3、有向图：由顶点和弧组成的图；无向图：由顶点和边组成的图。 4、完全有向图：n个顶点有n(n-1)个弧；完全无向图：n个顶点有n
1、从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。
1、假设由置换-选择得到9个初始归并段，其长度（即记录数）依次为：9,30,12,18,3,17,2,6,24。现作3-路平衡归并，其归并树（表示归并过程的图）如下图所示，
Huffman tree 基本术语 路径和路径长度 - 路径：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路。 - 结点的路径长度：从一个结点到另一个结点的路径上分支的数目。 结点的权及带权路径长度 - 结点的权:将树中结点赋予一个有着某种含义的数值。 - 结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度 - 树中所有叶子结点的带权路径长度之和。 赫夫曼树（ Huffman tree ） - 带权路径长度达到最小的二叉树即为赫夫曼
PHP数据结构（二十六）——基数排序实现36进制数排序 （原创内容，转载请注明来源，谢谢） 一、概述 插入排序、选择排序、快速排序等，都是通过关键字之间的比较和移动进行的。基数排序完全不同，其是借助多个关键字排序的思想对单逻辑关键字进行排序的方法。 所谓多关键字，可以理解为带权值的关键字。例如： 现有序列{a0,a1,a2,a3,b0,b1,b2,b3}，假设a<b，数字按数字正常的大小。现要求对这个序列进行排序，但是要求数字的优先级更高，即a0<b0<a1<b1。则这种排序可以认为是多关键字的排序
例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子
* **最优二叉树：**树的带权路径长度为树中所有叶子结点的带权路径长度之和最小。
无论是在我们的开发项目中，还是在我们的日常生活中，都会较多的涉及到文件压缩。谈到文件压缩，可能会有人想问文件压缩到底是怎么实现的，实现的原理是什么，对于开发人员来说，怎么实现这样一个压缩
树（一对多的数据结构） 树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种： （1）有且仅有一个特定的称为根（Root）的结点； （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。 对于树的定义还需要强调两点： 1.n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。 2.m>0时，子树的个数没有限制，但它们一定是互不相交的。 结点分类： 结点拥有的子
终于有机会重新回头学习一下一直困扰自身多年的数据结构了，赶脚棒棒哒。一直以来，对数据结构的掌握基本局限于线性表，稍微对树有一丢丢了解，而对于图那基本上就是不懂（不可否认，很多的考试中回避了图也是原因之一），而查找和排序只能算是了解点皮毛，简单的面试能应付的水平。关于数据结构方面的教材和视频有不少，首推严蔚敏老教授的书和视频，尤其是视频，记载的是其在清华大学的授课过程，全程通过不同的教具来演示不同的示例，非常直观。自身由于懒惰，一直也没坚持的把其看完，于是选择了相对简单的学习方法，就是选择了程杰老师的《大话数
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
云直播
对象存储
