1/26选择排序之堆排序主讲人: 程玉胜2013.12.20数据结构精品资源共享课2/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序3/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序4/26提高排序的速度待排序的数据具有什么特征时，排序的 速度加快？ 思考减少关键码间的比较次数最小值的同时，找出较小值18203236452538504028加快排序速度 知识点引入 堆定义及其存储 建堆 堆排序5/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序6/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序7/26堆的定义 知识点引入 堆定义及其存储 建堆 堆排序堆是具有下列性质的完全二叉树：每个结点的值都 小于或等于其左右孩子结点的值（称为小根堆）， 或每个结点的值都大于或等于其左右孩子结点的值 （称为大根堆）。182032364525385040281. 小根堆的根结点是 所有结点的最小者。 2. 较小结点靠近根结 点，但不绝对。503845402836322018281. 大根堆的根结点是 所有结点的最大者。 2. 较大结点靠近根结 点，但不绝对。8/26堆存储 知识点引入 堆定义及其存储 建堆 堆排序将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用顺序存储9/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序10/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序11/26堆排序的基本思想 知识点引入 堆定义及其存储 建堆 堆排序基本思想：首先将待排序的记录序列构造成堆（大根 堆），得到所有记录的最大者，然后将它从堆中移走 ，并将剩余的记录再调整成堆，这样又找出了次小者 ，以此类推，直到堆中只有一个记录。 u 1、如何从无序序列建成堆？关键问题u 2、根结点【最大（小）】怎么处理？u 3、如何重建堆？12/26堆调整的基本方法 知识点引入 堆定义及其存储 建堆 堆排序堆调整：假设根结点左右子树均是堆，如何调整根结点 ，使之成堆？28363216183032161830362832161828363013/26堆调整的基本方法 知识点引入 堆定义及其存储 建堆 堆排序void sift ( int r , int k, int m ) /要筛选结点的编号为k，堆中最后一个结点的编号为m i=k; j=2*i; temp=ri; /将筛选记录暂存while (jrj) break; else ri=rj; i=j; j=2*i;ri=temp; /将筛选记录移到正确位置 14/26建堆 知识点引入 堆定义及其存储 建堆 堆排序u 1、如何从无序序列建成一个堆？假设为28，25，16，36，18，3228251632183616最后一个结点（叶子）的序号是n ，则最后一个分支结点即为结点n 的双亲，其序号是n/2。将无序序列按照完全二叉树的形式构造 第一步算法描述：for (i=n/2; i=1; i-)sift(r, i, n) ; 15/26建堆 知识点引入 堆定义及其存储 建堆 堆排序u 1、如何从无序序列建成一个堆？假设为28，25，16，36，18，32 28251632183616321628251836253216281836252832362816182516/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序17/26内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序18/26堆排序 知识点引入 堆定义及其存储 建堆 堆排序u 2、根结点【最大（小）】怎么处理？32362816182536 28 32 25 18 161 2 3 4 5 6对 应交换16 28 32 25 18 361 2 3 4 5 6对 应32162836182519/26堆排序 知识点引入 堆定义及其存储 建堆 堆排序u 2、根结点【最大（小）】怎么处理？算法描述：r1rn-i+1; 解决方法：第 i 次处理堆顶是将堆顶记录r1与序列中第n-i+1个 记录rn-i+1交换。20/26堆排序 知识点引入 堆定义及其存储 建堆 堆排序u 3、如何重建堆？3216283618251628163236182528323618162521/26堆排序 知识点引入 堆定义及其存储 建堆 堆排序u 3、如何重建堆？解决方法：第 i 次调整剩余记录，此时，剩余记录有n-i个，调整 根结点至第n-i个记录。算法描述：sift(r, 1, n-i);22/26堆排序 知识点引入 堆定义及其存储 建堆 堆排序u 3、如何重建堆？void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆sift(r, i, n) ; for (i=1; in; i+ )r1rn-i+1; /移走堆顶sift(r, 1, n-i); /重建堆 从下到上从上到下23/26思考题 知识点引入 堆定义及其存储 建堆 堆排序已知一组键值序列 （32，44，38，65，53，42，29，57）， 试采用堆排序法对该组序列作升序排序， 给出建立的初始堆 以及第一次输出堆元素后筛选调整的堆（最 先调整的是哪个数） 3244386553422957576529382932296565323865思考题 知识点引入 堆定义及其存储 建堆 堆排序已知关键序列5，8，12，19，28，20，15，22是小根 堆（最小堆），插入关键字3，调整后得到的小根堆是A3，5，12，8，28，20，15，22，19 B. 3，5，12，19，20，15，22，8，28 C3，8，12，5，20，15，22，28，19 D. 3，12，5，8，28，20，15，22，19A思考题 知识点引入 堆定义及其存储 建堆 堆排序问题. 给定一个序列 43, 71, 86, 13, 38, 60, 27 ，给出堆排序前三趟的结果。 解析：26/26谢谢 !欢迎通过数据结构精品课程网站http:/210.45.168.34:8080/08/sjjg/Learning/SelfLearningDS/index.aspThanks for Your Attention