Chapter9 Priority Trees 堆(Heaps) 左高树(Leftist Trees) 11/19/2018

本章重点 堆的实现 堆排序 左高树 霍夫曼编码 11/19/2018

优先队列 与FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。 例。 11/19/2018

优先队列 优先队列是0个或多个元素的集合，每个元素都有一个优先权或值。 对优先队列执行的操作有1) 查找；2) 插入一个新元素；3) 删除 11/19/2018

优先队列的线性表描述 描述最大优先队列最简单的方法是采用无序线性表。 假设有一个具有n 个元素的优先队列，插入操作可以十分容易地在表的右端末尾执行，插入所需时间为Θ(1)。删除操作时必须查找优先权最大的元素，即在未排序的n 个元素中查找具有最大优先权的元素，所以删除操作所需时间为Θ(n)。 11/19/2018

优先队列的线性表描述 如果利用链表，插入操作在链头执行，时间为Θ(1)，而每个删除操作所需时间为Θ(n)。 11/19/2018

优先队列的线性表描述 另一种描述方法是采用有序线性表，当使用公式化描述时元素按递增次序排列，使用链表时则按递减次序排列，这两种描述方法的删除时间均为Θ(1)，插入操作所需时间为Θ(n)。 11/19/2018

最大树 定义 每个节点的值都大于或等于其子节点（如果有的话）值的树。 11/19/2018

最大树 11/19/2018

最小树 定义 每个节点的值都小于或等于其子节点（如果有的话）值的树。 11/19/2018

最小树 11/19/2018

最大堆(最小堆) 定义 最大（最小）的完全二叉树。 11/19/2018

最大堆的插入 11/19/2018

插入时间复杂性 插入策略从叶到根只有单一路径，每一层的工作需耗时Θ(1)，因此实现此策略的时间复杂性为O(height)=O(log2n)。 11/19/2018

最大堆的删除 11/19/2018

最大堆的删除 11/19/2018

删除时间复杂性 删除策略产生了一条从堆的根节点到叶节点的单一路径，每层工作需耗时Θ(1)，因此实现此策略的时间复杂性为O(height)=O(log2n)。 11/19/2018

最大堆的初始化 开始时堆中已经含有n (n >0) 个元素。可以通过在初始为空的堆中执行n 次插入操作来构建非空的堆，插入操作所需总时间为O(nlogn) 。 11/19/2018

思考 更快的堆的初始化策略？ 11/19/2018

思想 从第一个具有孩子的节点开始，这个元素在数组中的位置为i=[n/2]，如果以这个元素为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。 随后，继续检查以i-1,i-2等节点为根的子树，直到检查到整个二叉树的根节点（其位置为1）。 11/19/2018

最大堆的初始化 11/19/2018

最大堆的初始化 11/19/2018

类MaxHeap template<class T> class MaxHeap { public : MaxHeap(int MaxHeapSize = 10); ~MaxHeap() {delete [] heap;} int Size() const {return CurrentSize;} T Max() {if (CurrentSize == 0) throw OutOfBounds(); return heap[1];} MaxHeap<T>& Insert(const T& x); MaxHeap<T>& DeleteMax(T& x); void Initialize(T a[], int size, int ArraySize); private : int CurrentSize, MaxSize; T *heap; // 元素数组 } ; 11/19/2018

最大堆的插入 template<class T> MaxHeap<T>& MaxHeap<T>::Insert(const T& x) {//把x插入到最大堆中 if (CurrentSize==MaxSize) throw NoMem(); //为x寻找相应插入位置 //i从新的叶节点开始，并沿着树上升 int i=++CurrentSize； while (i!=1 && x>heap[i/2]){ //不能把x放入heap[i] heap[i]=heap[i/2]; i/=2; } heap[i]=x; return *this; 11/19/2018

最大堆的删除 template<class T> MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x) {//将最大元素放入x，并从堆中删除最大元素 //检查堆是否为空 if (CurrentSize==0) throw OutOfBounds(); //队列空 x=heap[1];//最大元素 //重构堆 T y=heap[CurrentSize--];//最后一个元素 //从根开始，为y寻找合适的位置 int i=1, //堆的当前节点 ci=2;//i的孩子 11/19/2018

最大堆的删除 while (ci<=CurrentSize) { //heap[ci]应该是i较大的孩子 if(ci<CurrentSize && heap[ci]<heap[ci+1]) ci++; //能把y放入heap[i]吗？ if (y>=heap[ci]) break; //能 //不能 heap[i]=heap[ci]; i=ci; ci*=2; } heap[i]=y; return *this; 11/19/2018

Leftist Trees(左高树) 堆结构是一种隐式数据结构，用完全二叉树表示的堆在数组中是隐式存贮的。由于没有存贮结构信息，这种描述方法空间利用率很高。 尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左高树就能满足这种要求。 11/19/2018

扩充二叉树 一棵二叉树，它有一类特殊的节点叫做外部节点(external node)，用来代替树中的空子树，其余节点叫做内部节点(internal node)。 增加了外部节点的二叉树被称为扩充二叉树(extended binary tree)。 11/19/2018

扩充二叉树 11/19/2018

s 令s(x)为从节点x 到它的子树的外部节点的所有路径中最短的一条，根据s(x)的定义可知，若x是外部节点，则s的值为0，若x为内部节点，则它的s值是： min{s(L),s(R)} + 1 其中L与R分别为x 的左右孩子。 11/19/2018

扩充二叉树的s和w 11/19/2018

高度优先左高树 定义 当且仅当一棵二叉树的任何一个内部节点，其左孩子的s 值大于等于右孩子的s 值时，该二叉树为高度优先左高树（height-biased leftist tree, HBLT）。 11/19/2018

高度优先左高树-性质 定理9-1 令x 为一个HBLT的内部节点，则 以x 为根的子树的节点数目至少为2s(x)-1。 若子树x 有m 个节点，s(x)最多为log2(m+1)。 通过最右路径（即，此路径是从x 开始沿右孩子移动）从x 到达外部节点的路径长度为s (x)。 11/19/2018

最大HBLT/最小HBLT [最大HBLT] 即同时又是最大树的HBLT； [最小HBLT] 即同时又是最小树的HBLT。 11/19/2018

最大HBLT的操作 插入 删除 合并 初始化 11/19/2018

最大HBLT的插入 最大HBLT的插入操作可借助于最大HBLT的合并操作来完成。 假设将元素x插入到名为H的最大HBLT中，如果建造一棵仅有一个元素x的最大HBLT然后将它与H进行合并，结果得到的最大HBLT将包括H中的全部元素及元素x。因此插入操作只需先建立一棵仅包含欲插入元素的HBLT，然后将它与原来的HBLT合并即可。 11/19/2018

最大HBLT的删除 根是最大元素，如果根被删除，将留下分别以其左右孩子为根的两棵HBLT的子树。将这两棵最大HBLT合并到一起，便得到包含除删除元素外所有元素的最大HBLT。 所以删除操作可以通过删除根元素并对两个子树进行合并来实现。 11/19/2018

合并两棵最大HBLT 具有n个元素的最大HBLT，其最右路径的长度为O(logn)。合并操作仅需遍历欲合并的HBLT的最右路径。由于在两条最右路径的每个节点上只需耗时O(1)，因此将两棵HBLT进行合并具有对数复杂性。 通过以上观察，在合并算法中，仅需移动右孩子。 11/19/2018

合并两棵最大HBLT 合并策略最好用递归来实现。 令A、B为需要合并的两棵最大HBLT，如果其中一个为空，则将另一个作为合并的结果，因此可以假设两者均不为空。 为实现合并，先比较两个根元素，较大者作为合并后的HBLT的根。假定A具有较大的根，且其左子树为L，C是由A的右子树与B合并而成的HBLT。A与B合并所得结果即是以A的根为根，L与C为左右子树的最大HBLT。如果L的s值小于C的s值，则C为左子树，否则L为左子树。 11/19/2018

最大HBLT的合并 11/19/2018

最大HBLT的合并 11/19/2018

初始化最大HBLT 通过将n个元素插入到最初为空的最大HBLT中来对其进行初始化，所需时间为O(nlogn)。 更快的方法？ 11/19/2018

初始化最大HBLT 为得到具有线性时间的初始化算法，首先创建n个最大HBLT，每个树中仅包含n个元素中的某一个，这n棵树排成一个FIFO队列，然后从队列中依次删除两个HBLT，将其合并，然后再加入队列末尾，直到最后只有一棵HBLT。 11/19/2018

例 构造五个元素：7,1,9,11,2的一棵最大HBLT。 首先构造五个单元素的最大HBLT，并形成一个FIFO队列。 11/19/2018

合并两棵左高树 template<class T> void MaxHBLT<T>::Meld(HBLTNode<T>* &x,HBLTNode<T>* y) {//合并两棵根分别为*x和*y的左高树，返回指向新根x的指针 if(!y) return; if(!x) {x=y; return;} if(x->data < y->data) Swap(x,y); Meld(x->RightChild,y); if(!x->LeftChild) {x->LeftChild=x->RightChild; x->RightChild=0; x->s=1;} else{ if(x-> LeftChild->s < x-> RightChild->s ) Swap(x-> LeftChild, x-> RightChild); x->s= x-> RightChild->s +1; } 11/19/2018

从最大HBLT中删除最大元素 template<class T> MaxHBLT<T>& MaxHBLT<T>::DeleteMax(T& x) {//删除最大元素，并将其放入x if(!root) throw OutOfBounds(); x=root->data;//最大元素 HBLTNode<T> *L=root->LeftChild; HBLTNode<T> *R=root->RightChild; delete root; root=L; Meld(root,R); return *this; } 11/19/2018

最大HBLT的初始化 template<class T> void MaxHBLT<T>::Initialize(T a[], int n) {//初始化有n个元素的HBLT树 Queue<HBLTNode<T> *> Q(n); Free(root);//删除老节点 //对树的队列进行初始化 for (int i=1;i<=n;i++){ HBLTNode<T> *q=new HBLTNode<T> (a[i],1); Q.Add(q);} HBLTNode<T> *b,*c; for (i=1;i<=n-1;i++) {Q.Delete(b).Delete(c); Meld(b,c); Q.Add(b);} if (n) Q.Delete(root); } 11/19/2018

应用 堆排序(Heap Sort) 机器调度(Machine Scheduling) 霍夫曼编码(Huffman Codes) 11/19/2018

堆排序 先将要排序的n 个元素初始化为一个最大堆，然后每次从堆中提取（即删除）元素。各元素将按递减次序排列。 初始化所需要的时间为(n)，每次删除所需要的时间为O(logn) ，因此总时间为O(nlogn) 。 11/19/2018

堆排序算法实现 template <class T> void HeapSort(T a[], int n) {// 利用堆排序算法对a[1:n] 进行排序 // 创建一个最大堆 MaxHeap<T> H(1); H.Initialize(a,n,n) ; // 从最大堆中逐个抽取元素 T x; for (int i = n-1; i >= 1; i--) { H.DeleteMax(x) ; a[i+1] = x; } 11/19/2018

堆排序算法实现 // 在堆的析构函数中保存数组a H.Deactivate(x) ; } 11/19/2018

堆排序 11/19/2018

例-压缩 假设文本是由a,u,x,z组成的字符串，若这个字符串的长度为1000，每个字符用一个字节来存贮，共需1000个字节（即8000位）的空间。如果每个字符用2位二进制来编码（00=a,01=x,10=u,11=z），则用2000位二进制即可表示1000个字符。 字符串aaxuaxz的压缩编码为二进制串0000011000011。 11/19/2018

例 此外，还需要一定的空间来存放编码表，可采用如下格式来存储： 符号个数,代码1,符号1,代码2,符号2,… 符号个数及每个符号分别用8位二进制来表示，每个代码需占用[log2(符号个数)]位二进制。因此，代码表需占用5*8+4*2=48位，压缩比为8000/2048=3.9。 11/19/2018

例-解压 字符串aaxuaxz的压缩编码为二进制串00000110000111，每个字符的编码具有相同的位数（两位）。 从左到右依次从位串中取出2位，通过查编码表便可获得原字符串。 11/19/2018

频率 一个字符出现的次数称为频率（frequency） 在字符串aaxuaxz中，a出现了三次。 a,x,u,z，在这个字符串中出现的频率分别为3，2，1，1。 11/19/2018

方案 采用可变长编码。 使用编码(0=a,10=x,110=u,111=z) 。如果四个字符的出现频率分别为(996,2,1,1)，则每个字符用2位编码所得到编码的长度为2000位，而用可变长编码则仅为1006位。 11/19/2018

解码依据 可变长编码:没有任何一个代码是另一代码的前缀。 因此，当从左到右检查代码时，可以很确定地得到与实际代码相匹配的字符。 11/19/2018

霍夫曼编码 可以利用扩充二叉树来派生一个实现可变长编码的特殊类，该类满足上述前缀性质，被称为霍夫曼编码。 11/19/2018

霍夫曼编码 在扩充二叉树中，可对从根到外部节点的路径进行编码，方法是向左孩子移动时取0，向右孩子移动时取1。 11/19/2018

霍夫曼编码 到节点(a,b,c,d,e,f)的路径编码分别为(00，010，011，100，101，11) 11/19/2018

加权外部路径长度 对于一棵具有外部节点1，… n 的扩充二叉树，对应的压缩编码串的长度为： 其中L(i) 为从根到达外部节点i 的路径长度（即路径的边数）；F(i)为外部节点i 的权值(压缩中字符的频率)；WEP为二叉树的加权外部路径长度（weighted external path length）。 11/19/2018

带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 具有不同带权路径长度的扩充二叉树 霍夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中，权值大的结点离根最近。 11/19/2018

霍夫曼树 若二叉树对于给定的频率具有最小加权外部路径长度，则这棵树被称为霍夫曼树（Huffman tree）。 11/19/2018

利用霍夫曼编码进行压缩 获得不同字符的频率。 建立具有最小加权外部路径的二叉树（即霍夫曼树），树的外部节点用字符串中的字符表示，外部节点的权重(weight)即为该字符的频率。 遍历从根到外部节点的路径得到每个字符的编码。 用字符的编码来代替字符串中的字符。 11/19/2018

构造霍夫曼树 为了构造霍夫曼树，首先从仅含一个外部节点的二叉树集合开始，每个外部节点代表字符串中一个不同的字符，其权重等于该字符的频率。 此后不断地从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树，合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根节点。新二叉树的权重为两棵子树的权重之和。 这个过程可一直持续到仅剩下一棵树为止。 11/19/2018

构造霍夫曼树 11/19/2018

构造霍夫曼树 权重=27。到节点(a,b,c,d,e,f)的路径编码分别为(00，010，011，100，101，11) 11/19/2018

霍夫曼树 霍夫曼树的建立过程可以利用最小堆来实现。 最小堆用来存贮二叉树集合。 最小堆中的每个元素包括一棵二叉树及其权重值， 11/19/2018

输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTree T, Stack& S ) { if (T) { Push( S, T->data ); if (!T->Lchild && !T->Rchild ) PrintStack(S); else { AllPath( T->Lchild, S ); AllPath( T->Rchild, S ); } Pop(S); } // if(T) } // AllPath 11/19/2018

输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTree T, Stack& S, bool flag ) { if (T) { if (T->data ) {PrintStack(S);} else {if (flag ) {Push( S, 0 ); AllPath( T->Lchild, S,0 );} else { Push( S, 1 ); AllPath( T->Rchild, S ,1); } }} Pop(S); } // if(T) } // AllPath 11/19/2018

作用 1、编码 2、优化程序 3、归并排序 11/19/2018

字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。 11/19/2018

化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。 A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码是一种无 前缀编码。解码时不会 混淆。 霍夫曼编码树 11/19/2018

编制分数转化程序 if (a<60) b=‘不及格’ else if (a<70) b=‘及格’ else b=‘优秀’ 11/19/2018

作业 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 11/19/2018

A<60 N Y A<70 不及格 N Y 及格 A<80 N Y A<90 中等 N Y 良好 优秀 11/19/2018

70≤A<80 N Y 80≤A<90 中等 N Y 良好 60≤A<70 N Y A<60 及格 N Y 不及格 优秀 11/19/2018

A<80 N Y A<70 A<90 N Y Y N 中等 良好 优秀 A<60 N Y 及格 不及格 10000个输入，各需要多少次比较 11/19/2018

归并排序 练习23 11/19/2018

11/19/2018