第1章-数据结构1

2020年5月28日星期四1高等数据结构与算法:优先队列©骆嘉伟计算机与通信学院湖南大学[e-mail]2020年5月28日星期四21引言定义[优先队列]优先队列（priorityqueue）是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1)查找；2)插入一个新元素；3)删除。最小优先队列（minpriorityqueue）:查找操作用来搜索优先权最小的元素，删除操作用来删除该元素最大优先队列（maxpriorityqueue）:查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。引言2020年5月28日星期四31引言最大优先队列的抽象数据类型描述抽象数据类型MaxPriorityQueue{实例有限的元素集合，每个元素都有一个优先权操作Create()：创建一个空的优先队列Size()：返回队列中的元素数目Max()：返回具有最大优先权的元素Insert(x)：将x插入队列DeleteMax(x)：从队列中删除具有最大优先权的元素，并将该元素返回至x}引言2020年5月28日星期四42线性表采用无序线性表假设有一个具有n个元素的优先队列，那么插入操作可以十分容易地在表的右端末尾执行，插入所需时间为(1)。删除操作时必须查找优先权最大的元素，即在未排序的n个元素中查找具有最大优先权的元素，所以删除操作所需时间为(n)。如果利用链表，插入操作在链头执行，时间为(1)，而每个删除操作所需时间为(n)。采用有序线性表元素按递增次序排列，使用链表时则按递减次序排列，这两种描述方法的删除时间均为(1)，插入操作所需时间为(n)。线性表2020年5月28日星期四53堆定义[最大树（最小树）]每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。堆2020年5月28日星期四63堆定义[最大堆（最小堆）]最大（最小）的完全二叉树。堆2020年5月28日星期四73堆最大堆的插入堆2020年5月28日星期四83堆最大堆的删除堆2020年5月28日星期四93堆最大堆的初始化堆2020年5月28日星期四109.3堆堆2020年5月28日星期四113堆类MaxHeaptemplateclassTclassMaxHeap{public:MaxHeap(intMaxHeapSize=10);~MaxHeap(){delete[]heap;}intSize()const{returnCurrentSize;}TMax(){if(CurrentSize==0)throwOutOfBounds();returnheap[1];}MaxHeapT&Insert(constT&x);MaxHeapT&DeleteMax(T&x);voidInitialize(Ta[],intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;//元素数组}堆2020年5月28日星期四123堆最大堆的插入templateclassTMaxHeapT&MaxHeapT::Insert(constT&x){//把x插入到最大堆中if(CurrentSize==MaxSize)throwNoMem();//没有足够空间//为x寻找应插入位置//i从新的叶节点开始，并沿着树上升inti=++CurrentSize;while(i!=1&&xheap[i/2]){//不能够把x放入heap[i]heap[i]=heap[i/2];//将元素下移i/=2;//移向父节点}heap[i]=x;return*this;}堆2020年5月28日星期四133堆最大堆的删除templateclassTMaxHeapT&MaxHeapT::DeleteMax(T&x){//将最大元素放入x，并从堆中删除最大元素//检查堆是否为空if(CurrentSize==0)throwOutOfBounds();//队列空x=heap[1];//最大元素//重构堆Ty=heap[CurrentSize--];//最后一个元素//从根开始，为y寻找合适的位置inti=1,//堆的当前节点ci=2;//i的孩子堆2020年5月28日星期四143堆while(ci=CurrentSize){//heap[ci]应是i的较大的孩子if(ciCurrentSize&&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;}堆2020年5月28日星期四153堆初始化一个非空最大堆templateclassTvoidMaxHeapT::Initialize(Ta[],intsize,intArraySize){//把最大堆初始化为数组a.delete[]heap;heap=a;CurrentSize=size;MaxSize=ArraySize;//产生一个最大堆for(inti=CurrentSize/2;i=1;i--){Ty=heap[i];//子树的根//寻找放置y的位置堆2020年5月28日星期四163堆intc=2*i;//c的父节点是y的目标位置while(c=CurrentSize){//heap[c]应是较大的同胞节点if(cCurrentSize&&heap[c]heap[c+1])c++;//能把y放入heap[c/2]吗?if(y=heap[c])break;//能//不能heap[c/2]=heap[c];//将孩子上移c*=2;}//下移一层heap[c/2]=y;}}堆2020年5月28日星期四174左高树一棵二叉树，它有一类特殊的节点叫做外部节点,用来代替树中的空子树，其余节点叫做内部节点。增加了外部节点的二叉树被称为扩充二叉树.令s(x)为从节点x到它的子树的外部节点的所有路径中最短的一条，根据s(x)的定义可知，若x是外部节点，则s的值为0，若x为内部节点，则它的s值是：min{s(L),s(R)}+1其中L与R分别为x的左右孩子。定义[高度优先左高树]当且仅当一棵二叉树的任何一个内部节点，其左孩子的s值大于等于右孩子的s值时，该二叉树为高度优先左高树（height-biasedleftisttree,HBLT）。左高树2020年5月28日星期四184左高树左高树2020年5月28日星期四194左高树定义[最大HBLT]即同时又是最大树的HBLT。定义[最小HBLT]即同时又是最小树的HBLT。定义[重量优先左高树]当且仅当一棵二叉树的任何一个内部节点，其左孩子的w值大于等于右孩子的w值时，该二叉树为重量优先左高树（weight-biasedleftisttree,WBLT）。定义[最大（小）WBLT]即同时又是最大（小）树的WBLT。左高树2020年5月28日星期四204左高树合并策略：令A、B为需要合并的两棵最大HBLT，如果其中一个为空，则将另一个作为合并的结果，因此可以假设两者均不为空。为实现合并，先比较两个根元素，较大者作为合并后的HBLT的根。假定A具有较大的根，且其左子树为L，C是由A的右子树与B合并而成的HBLT。A与B合并所得结果即是以A的根为根，L与C为左右子树的最大HBLT。如果L的s值小于C的s值，则C为左子树，否则L为左子树。左高树2020年5月28日星期四214左高树左高树2020年5月28日星期四224左高树左高树2020年5月28日星期四234左高树初始化最大HBLT首先创建n个最大HBLT，每个树中仅包含n个元素中的某一个，这n棵树排成一个FIFO队列，然后从队列中依次删除两个HBLT，将其合并，然后再加入队列末尾，直到最后只有一棵HBLT。左高树2020年5月28日星期四244左高树构造具有五个元素：7,1,9,11,2的一棵最大HBLT。为此，首先构造五个单元素的最大HBLT，并形成一个FIFO队列。把最前面的两个最大HBLT7和1从队列中删除并进行合并，所得结果如图a所示，将该结果加入到队列中。接下来从队列中删除两棵最大HBLT9和11并进行合并，所得结果如图b所示，也将该结果加入队列中。现在继续从队列中删除最大HBLT2及图a所得到的HBLT，并进行合并，所得结果如图c所示加入队列。下一对从队列中删除的最大HBLT如图b与c所示，经合并得到的最大HBLT如图d所示，将该结果插入到队列中。至此，队列中只有一棵最大HBLT，初始化工作完成。左高树2020年5月28日星期四254左高树HBLT的节点类templateclassTclassHBLTNode{friendMaxHBLTT;public:HBLTNode(constT&e,constintsh){data=e;s=sh;LeftChild=RightChild=0;}private:ints;//节点的s值Tdata;HBLTNodeT*LeftChild,*RightChild;};左高树2020年5月28日星期四264左高树MaxHBLT类templateclassTclassMaxHBLT{public:MaxHBLT(){root=0;}~MaxHBLT(){Free(root);}TMax(){if(!root)throwOutOfBounds();returnroot-data;}MaxHBLTT&Insert(constT&x);MaxHBLTT&DeleteMax(T&x);MaxHBLTT&Meld(MaxHBLTT&x){Meld(root,x.root);x.root=0;return*this;}voidInitialize(Ta[],intn);private:voidFree(HBLTNodeT*t);voidMeld(HBLTNodeT*&x,HBLTNodeT*y);HBLTNodeT*root;//指向树根的指针};左高树2020年5月28日星期四274左高树合并两棵左高树templateclassTvoidMaxHBLTT::Meld(HBLTNodeT*&x,HBLTNodeT*y){//合并两棵根分别为*x和*y的左高树//返回指向新根x的指针if(!y)return;//y为空if(!x)//x为空{x=y;return;}//x和y均为空if(x-datay-data)Swap(x,y);//现在x-data=y-dataMeld(x-RightChild,y);左高树2020年5月28日星期四284左高树if(!x-LeftChild){//左子树为空//交换子树x-LeftChild=x-RightChild;x-RightChild=0;x-s=1;}else{//检查是否需要交换子树if(x-LeftChild-sx-RightChild-s)Swap(x-LeftChild,x-RightChild);x-s=x-RightChild-s+1;}}左高树2020年5月28日星期四294左高树最大HBLT的插入templateclassTMaxHBLTT&MaxHBLTT::Insert(constT&x){//把x插入到左高树中//创建带有一个节点的树HBLTNodeT*q=newHBLTNodeT(x,1);//把q与原树进行合并Meld(root,q);return*this;}左高树2020年5月28日星期四305应用1-堆排序先将要排序的n个元素初始化为一个最大堆，然后每次从堆中提取（即删除）元素。各元素将按递减次序排列。templateclassTvoidHeapSort(Ta[],intn){//