数据结构与算法b-2014年4月30日课堂

数据结构与算二叉主讲 建堆不必将值一个个 堆中，通过交换形成堆假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：(1)R的值小于或等于其两 ，此时堆已完成(2)R的值大于其某一个或全部两个 中值较小的一个交换，结果得到一个堆，除 信息学 Page图示R信息学 Page堆的类定template<classT>classMinHeap{T*heapArray; int //当前堆中元素数intMaxSize; voidBuildHeap(); MinHeap(constintn)；//初始化堆的最大元素数目virtual~MinHeap(){delete[]heapArray;//析构函数信息学 PageboolisLeaf(intpos)//返回左孩子位intleftchild(intpos)//返回右孩子位intrightchild(intpos)返回父结点位intparent(intpos)信息学 Page//删除给定下标的元boolRemove(intpos,T&//向堆 新元素boolInsert(constT&T&RemoveMin()；voidSiftUp(intposition);voidSiftDown(intleft)； 信息学 Page堆成MinHeap<T>::MinHeap(constintn){ heapArray=newT[MaxSize]; //此处进行堆元素的赋值工}信息学 Pagetemplate<classboolMinHeap<T>::isLeaf(intpos){}所有i>n/2-1的结点都没有 堆的建立应从n/2-1开始，不断递减结点下信息学

Pagetemplate<classintMinHeap<T>::leftchild(intpos){return //返回左孩子位template<classT>intMinHeap<T>::rightchild(intpos){return //返回右孩子位template<classT>intMinHeap<T>::parent(intpos){return(pos- //返回父结点位信息学 Pagetemplate<classvoidMinHeap<T>::SiftDown(int{int //T //int //j将标识关键值较小的子结while(j<CurrentSize)信息学 Pageif((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1])) //j指向数值较小的子结if(temp>heapArray[j]){ //向下继}else}//while信息学 Pagetemplate<classvoid{//反复调用筛选函for(inti=CurrentSize/2-1;i>=0;i--)}信息学 Pagetemplate<classvoidMinHeap<T>::SiftUp(int{intTtemp=heapArray[temppos];while((temppos>0)&&{} 信息学 Pagetemplate<classboolMinHeap<T>::Insert(constT&{if(CurrentSize==MaxSize)//returnFALSE; }信息学 Page从最(优先队列出队要求保持完全二叉树形状，并且剩下的n-1个结点值仍然符合堆的性质。可以将堆中最后一个位置上的元素(数组中实际的最后一个元素)移到根的位置上，利用siftdown对堆重新调整。T&{{//空cout<<"Can't}信息学 Page{//交换堆顶和最后一个元 <=1就不要调整了//从堆顶开始筛return}//end}信息学 Pagetemplate<class

boolMinHeap<T>::Remove(intpos,T&{returnfalse;//指定元素置于最T return}信息学 Page建堆n个结点的堆，深度dlog2(n+1)-1。根为第层，则第i层(除最深一层)结点个数为2i大约一半的结点深度为d-1(或d)，不移动(叶子约1/4结点深度为d-2(或d-1）每向上一层，结点的数目为前一层的一半，而子树高度加一。元素移动的最大距离的总数为log

i

O所有i>n/2-1的结点都没 结点，所北堆的建立应从n/2-1北建堆建堆算法的时间代价为由于堆logn层深，结点、删除普通元素和删除最小元素的平均时间代价和时间代价(logn)信息学 Page优先有些优先队列的应用要求能够改变已于队列中的对象的优先权，典型实现方法需要一个辅助数据结构（二叉搜索树）。信息学 Page大4.1二叉树的概4.24.3二叉树的抽4.4周游二叉4.5二叉树的实4.6二叉搜索4.7堆与优先队4.8Huffman编码信息学 PageHuffman构造一个具有n每个外部结点Ki有一个wi对应，作为该外部结点的这个扩充二叉树的叶结点带权外部路径长度总和最i0argmin(n1wii0信息学 Page设D={d0，…，dn－1}，通信编码总长最短didj则di的编码不能是dj的编码的前缀，反之亦然信息学 Page前缀一个编码集合中，任何一个字符的编码都不会是另外一个字符编码的前缀，这种编码叫作前缀编码。前缀特性保证代码串例8Z(111100),K(111101),F(11111),C(1110),U(100),D(101),L(110),E(0)对于代码 出唯一的字符串信息学 Page用d0，d1，…，dn－1作外部结点，W0，W1，…，Wn－1作把从每个结点引向其左的边标上号码0，把从每个结点引向其右的边标上号码1。从根到每个叶子的路径上的信息学 Page各字d8：出现信息学 Page从二叉树的根开始，用需要译码的二进制位串中的若干个相邻位与二叉树边上标的0、1相匹配，确定一条到达树叶的路径。一旦到达树叶，则译出了一个字符。信息学 Page构造HuffmanStep1照“权”(频率)将字符排Step2:取走“权”最小的两个字符，构造一个新元素，将这两个字符标为这个元素的左右；该元Step3:若序列中只剩一个元素，则Huffman树构造完毕,退出；否则，返回Step2。信息学 Page信息学 PageHuffman树template<classT>classHuffmanTree{HuffmanTreeNode<T>* //Huffman树的树//把ht1和ht2为根的Huffman子//合并成一棵以parent为根的二叉voidMergeTree(HuffmanTreeNode<T>&HuffmanTreeNode<T>&HuffmanTreeNode<T>*parent信息学 Page//删除Huffman树或其子voidDeleteTree(HuffmanTreeNode<T>*root)；//构造函数，weight 权值的数组，n是数组长HuffmanTree(Tweight[],int//析构函virtual~HuffmanTree()}信息学 PageHuffmantemplate<classT>HuffmanTree<T>::HuffmanTree(Tweight[],intn){MinHeap<HuffmanTreeNode<T>>heap(n);*parent,&firstchild,&secondchild;HuffmanTreeNode<T>*NodeList=new