堆和堆排序在笔试题面试题中的应用20220727.docx
A.的硬件实现比哈夫曼编码的硬件实现要复杂
B.在信源符号概率接近时，比哈夫曼编码效率高
C.在JPEG的扩展系统中被推荐来代替哈夫曼编码
D.中不存在源符号和码字间一一对应关系
下面关于哈夫曼树的叙述中，正确的是()
A.哈夫曼树一定是完全二叉树
B.哈夫曼树一定是平衡二叉树
C.哈夫曼树中权值最小的两个节点互为兄弟节点
D.哈夫曼树中左孩子节点小于父节点、右孩子节点大于父节点
下面关于哈夫曼树的叙述中，正确的是(58)。
A．哈夫曼树一定是完全二叉树
B．哈夫曼树一定是平衡二叉树
C．哈夫曼树中权值最小的两个结点互为兄弟结点
D．哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
解析：哈夫曼树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。具有以下特征：
(1)当叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。即哈夫曼树不一定是完全二叉树。
(2)在最优二叉树中，权值越大的叶子离根越近。
(3)最优二叉树的形态不唯一，但WPL最小。
哈夫曼树的构造：
(1)根据给定的n个权值{w1，w2，…，wn}构造n棵二叉树的集合F={Tl，T2，…，Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
(2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右予树上根结点的权值之和。
(3)将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
(4)重复(2)和(3)直到F中只含一棵树为止，这棵树就是哈夫曼树。
平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。而哈夫曼树并未要求左右两个子树的高度差的绝对值不超过1，根据其构造可知，是从上往下顺序排下来的，且左孩子结点大于父孩子结点。
堆和堆排序在笔试题面试题中的应用堆和堆排序在题题中的应用; 使用堆解决可以解决下列几个问题, 它们在笔试面试题中可以称为经典和烫手的：构建哈夫曼代码怎样提升性能?我们知道在构建哈夫曼树时,每次要选择集合中两个最小的元 素，然后将元素值相加，合并为一个新节点，此时两个最小的元素的 取出可以用HeapExtractMin函数来实现产出的新节点需要插入到 堆中我们有MinHeapInsert函数来实现。之前我们遇到哈夫曼编码，往往关注的是其思想，然而每次取 出最小的2个元素的过程，却涉及到排序、求极值的问题。这时候用 堆来维护这个队列，每次还能将取出的两个最小值的和插到堆里，非 常方便，减少了运行时间。计算大型浮点数集合的和有一个很普遍的情况，我们知道浮点数的存储都有精度,遇到 大浮点数和小浮点数相加，很可能会造成精度误差。所以可以每次从 优先级队列中取出最小的两个数相加，和1的实现差不多。在具有10亿个数值的集合中找到100万个最大的数这个就是TOP(K)问题了，可以建立100万个元素的最小二叉 堆，后面的数和根部进行比较，如果大于根部，进行堆调整将多个小型有序文件合并到一个大型有序文件中该问题我整理成了另一篇文章。里面附有源码测试;假设有n个小型有序文件，建立一个大小为n的最小堆，每 个有序文件贡献一个（如果有的话）,每次取出最小值插入到大型文件 中，并且去掉该最小元素，并将它在文件中的后续元素插入到堆中, 能够在o（lgn）的时间内从n个文件中选择要插入到大型文件中的元 素。意思就是，维护一个堆，该堆存放了所有小文件的最小值。每 次取出最小值min（属于小文件A）,将小文件A的下一个最小值再插 入到A。持续下去,问题解决。其他的相关:
以下关于哈夫曼树的叙述，正确的是（60）。
A.哈夫曼树一定是满二叉树，其每层结点数都达到最大值
B.哈夫曼树一定是平衡二叉树，其每个结点左右子树的高度差为-1、0或1
C.哈夫曼树中左孩子结点的权值小于父节点、右孩子节点的权值大于父节点
D.哈夫曼树中叶子节点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。所以D选项的说法正确。
下列关于哈夫曼树的叙述错误的是
A．一棵哈夫曼树是带权路径长度最短的二叉树
B．一棵哈夫曼树中叶节点的个数比非叶节点的个数大1
C．一棵哈夫曼树节点的度要么是0，要么是2
D．哈夫曼树的根节点的权值等于各个叶节点的权值之和
解析：哈夫曼树中节点的度可以是0，1，2。
下列关于哈夫曼树的叙述错误的是
A．一棵哈夫曼树是带权路径长度最短的二叉树
B．一棵哈夫曼树中叶结点的个数比非叶结点的个数大1
C．一棵哈夫曼树结点的度要么是0，要么是2
D．哈夫曼树的根结点的权值等于各个叶子结点的权值之和
解析：哈夫曼树中结点的度可以是0，1，2。
● 下面关于哈夫曼树的叙述中，正确的是 （58） 。
（58）
A. 哈夫曼树一定是完全二叉树
B. 哈夫曼树一定是平衡二叉树
C. 哈夫曼树中权值最小的两个结点互为兄弟结点
D. 哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
B.在哈夫曼树中，权值较大的叶子结点一般离根结点较远
C.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近
D.在哈夫曼编码中，当两个字符出现频率相同时，其编码也相同，对于这种情况应作特殊外理