数据结构与算法 (28).pdf
9.1 二叉排序树9.2 二叉平衡树9.3 堆和堆排序第9章 基于二叉树的查找与排序 9.3.1 堆和堆排序的概念9.3.2 堆的调整9.3.3 建堆9.3.4 堆排序9.3 堆和堆排序 堆的定义若n个元素的序列a1a2 an 满足ai a2i 或或ai a2iai a2i+1ai a2i+1则分别称该序列则分别称该序列aa1 1a a2 2 a an n 为为小根堆小根堆 或或大根堆。大根堆。从堆的定义可以看出从堆的定义可以看出，堆实质是满足双亲节点堆实质是满足双亲节点大于大于（或小于或小于）孩子节点性质的完全二叉树孩子节点性质的完全二叉树42212403034365041小根(顶)堆12223440303650410 1 2 3 4 5 6 7 8 小根堆例子55087403036341222大根(顶)堆87503640303412220 1 2 3 4 5 6 7 8 大根堆例子【例例】下面序列为堆，对应的完全二叉树分别为:9877356255143548(a)一个大根堆1448356255983577(b)一个小根堆9877 35 62 55 14 35 4814 48 35 62 55 98 35 779877356255143548(a)一个大根堆1448356255983577(b)一个小根堆若在输出堆顶的最小值若在输出堆顶的最小值（最大值最大值）后后，使得剩使得剩余余n n-1 1个元素的序列重又建成一个堆个元素的序列重又建成一个堆，则得到则得到n n个个元素的次小值元素的次小值（次大值次大值）如此反复如此反复，便能得便能得到一个有序序列到一个有序序列，这个过程称之为这个过程称之为堆排序堆排序。堆排序85087403036341222502240303634128787503640303412222250364030341287 利用大根堆进行排序的示例演示实现堆排序需解决两个问题：实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？下面先讨论第二个问题：下面先讨论第二个问题：9.3.1 堆和堆排序的概念 9.3.2 堆的调整9.3.3 建堆9.3.4 堆排序9.3 堆和堆排序如何在输出堆顶元素后，调整剩余元素为一个如何在输出堆顶元素后，调整剩余元素为一个新的堆？新的堆？解决方法：从堆顶至叶子解决方法：从堆顶至叶子“筛选”“筛选”输出堆顶元素之后，以堆中最后一个元素替代输出堆顶元素之后，以堆中最后一个元素替代之；之；然后将根结点值与左、右子树的根结点值进行然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；比较，并与其中小者进行交换；重复上述操作，直至叶子结点，或一次比较过重复上述操作，直至叶子结点，或一次比较过程中没有交换，将得到新的堆程中没有交换，将得到新的堆133827497665499713输出根并以最后一个元素代替之；比较其左右孩子值的大小，并与其中较小者交换；9727974997小根堆typedef struct node ElementType*data;/*存储元素的数组存储元素的数组*/int Size;/*堆中当前元素个数堆中当前元素个数*/Hnode,*Heap;/*堆的类型定义堆的类型定义*/堆的类型定义void HeapAdjust(Heap H,int s,int m)/*下滤：将下滤：将H中以中以H-Datap为根的子堆调整为最大堆为根的子堆调整为最大堆*/int Parent,Child;ElementType X;X=H-Datas;/*取出根结点存放的值取出根结点存放的值*/for(Parent=s;Parent*2DataChildDataChild+1)Child+;/*Child指向左右子结点的较大者指向左右子结点的较大者*/if(X=H-DataChild)break;/*找到了合适位置找到了合适位置*/else/*下滤下滤X*/H-DataParent=H-DataChild;H-DataParent=X;筛选算法筛选算法9.3.1 堆和堆排序的概念9.3.2 堆的调整 9.3.3 建堆9.3.4 堆排序9.3 堆和堆排序16对无序序列50，38，48，97，49，13，27，65进行堆排序。3850974948132765（2 2）从）从最后一个非终端结点最后一个非终端结点开始建堆；开始建堆；n n个结点个结点,最后一个非终端结最后一个非终端结点的下标是点的下标是 n/2n/2 建大根堆算法示例演示建大根堆算法示例演示例(1)(1)先建一个完全二叉树先建一个完全二叉树：173850974948132765385097494813276538509749481327653849976548132750 算法示例演示建小根堆示例472412853691305353363091471224850123456791853012301285911253125324532453例练习：将数列56，34，67，89，56，23，45，12构造成小根堆。（a）56 34 67 89 56 45 12 23 调整调整89（b）56 34 67 12 56 45 89 23 调整调整34（c）56 34 12 56 45 89 23 67 调整调整67（d）56 23 56 45 67 89 12 34 调整调整56（e）56 56 45 89 23 67 12 34 4938659776132749 首先首先，调整从第调整从第n/n/2 2个元素开始个元素开始将以该元素为根的二叉树调整为将以该元素为根的二叉树调整为堆堆 然后然后，将以序号为将以序号为n/n/2 21 1的结点的结点为根的二叉树调整为堆；为根的二叉树调整为堆；再将以序号为再将以序号为n/n/2 22 2的结点为根的结点为根的二叉树调整为堆；的二叉树调整为堆；一直进行到二叉树中的第一个节一直进行到二叉树中的第一个节点；点；9749651349132749void MakeHeap(Heap H)/*调整调整H-Data中的元素，使满足最大堆的有序性中的元素，使满足最大堆的有序性*/int i;/*从最后一个结点的父节点开始，到根结点从最后一个结点的父节点开始，到根结点1*/for(i=H-Size/2;i0;i-)HeapAdjust(H,i,H-Size);建堆算法9.3.1 堆和堆排序的概念9.3.2 堆的调整9.3.3 建堆 9.3.4 堆排序9.3 堆和堆排序24堆排序的算法思想堆排序的算法思想(1 1)按关键字建立按关键字建立AA1 1,A,A2 2,AnAn的大根堆的大根堆;(2 2)输出堆顶元素输出堆顶元素，采用堆顶元素采用堆顶元素AA1 1 与最后一与最后一个元素个元素AnAn交换交换，最大元素得到正确的排序位置最大元素得到正确的排序位置;(3 3)此时前此时前n n-1 1个元素不再满足堆的特性个元素不再满足堆的特性，需重需重建堆建堆;(4 4)循环执行循环执行2 2,3 3两步两步，到排序完成到排序完成。111098765432111107710191913 83 43388 3 573 6337632652 421541 211431132112 堆排序过程示例堆排序过程示例void HeapSort(Heap H)int i;ElemType temp;for(i=H.Size/2;i1;-i)HeapAdjust(H,i,H.Size);/*利用利用HeapAdjust()，将将data1datan筛选成堆筛选成堆*/for(i=H.Size;i1;-i)/*堆顶元素堆顶元素data1与堆底元素与堆底元素datai交换交换*/temp=H.datai;H.datai=H.data1;H.data1=temp;HeapAdjust(H,1,i-1);/*利用利用HeapAdjust()，将将data1datai-1筛选成堆筛选成堆*/堆排序算法O(nlog2n)27 堆排序算法分析堆排序算法分析2，38，38382382383823838(1)(1)堆排序是堆排序是不稳定不稳定的排序。的排序。(2)(2)时间复杂度为时间复杂度为O(nlogO(nlog2 2n)n)。最坏情况下时间复杂度为最坏情况下时间复杂度为O(nlogO(nlog2 2n)n)的算法。的算法。(3)(3)空间复杂度为空间复杂度为O(1)O(1)。The end
