数据结构-堆排序.ppt

*/39 */26 选择排序之堆排序 主讲人: 程玉胜 2013.12.20 《数据结构》精品资源共享课 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 提高排序的速度 待排序的数据具有什么特征时，排序的速度加快？ 思考 减少关键码间的比较次数 最小值的同时，找出较小值 18 20 32 36 45 25 38 50 40 28 加快排序速度 知识点引入 堆定义及其存储 建堆 堆排序 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 堆的定义 知识点引入 堆定义及其存储 建堆 堆排序 堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 18 20 32 36 45 25 38 50 40 28 1. 小根堆的根结点是所有结点的最小者。 2. 较小结点靠近根结点，但不绝对。 50 38 45 40 28 36 32 20 18 28 1. 大根堆的根结点是所有结点的最大者。 2. 较大结点靠近根结点，但不绝对。 */26 堆存储 知识点引入 堆定义及其存储 建堆 堆排序 将堆用顺序存储结构来存储，则堆对应一组序列。 50 38 45 40 28 36 32 20 18 28 50 38 45 32 36 40 28 20 18 28 1 2 3 4 5 6 7 8 9 10 采用顺序存储 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 内容提要 知识点引入 堆定义及其存储 建堆 堆排序 知识点引入 堆定义及其存储 建堆 堆排序 */26 堆排序的基本思想 知识点引入 堆定义及其存储 建堆 堆排序 基本思想：首先将待排序的记录序列构造成堆（大根堆），得到所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小者，以此类推，直到堆中只有一个记录。 1、如何从无序序列建成堆？ 关键问题 2、根结点【最大（小）】怎么处理？ 3、如何重建堆？ */26 堆调整的基本方法 知识点引入 堆定义及其存储 建堆 堆排序 堆调整：假设根结点左右子树均是堆，如何调整根结 点 ，使之成堆？ 28 36 32 16 18 30 32 16 18 30 36 28 32 16 18 28 36 30 */26 堆调整的基本方法 知识点引入 堆定义及其存储 建堆 堆排序 void sift ( int r[ ], int k, int m ) {//要筛选结点的编号为k，堆中最后一个结点的编号为m i=k; j=2*i; temp=r[i]; //将筛选记录暂存 while (j=m ) //筛选还没有进行到叶子 { if (jm r[j]r[j+1]) j++; //左右孩子中取较大者 if (r[i]r[j]) break; else { r[i]=r[j]; i=j; j=2*i; } } r[i]=temp; //将筛选记录移到正确位置 } */26 建堆 知识点引入 堆定义及其存储 建堆 堆排序 1、如何从无序序列建成一个堆？ 假设为｛28，25，16，36，18，32｝ 28 25 16 32 18 36 16 最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点n的双亲，其序号是n/2。 将无序序列按照完全二叉树的形式构造 第一步 算法描述： for (i=n/2; i=1; i--) sift(r, i, n) ; */26 建堆 知识点引入 堆定义及其存储 建堆 堆排序 1、如何从无序序列建成一个堆？ 假设为｛28，25，16，36，18，32｝ 28 25