数据结构全套配套课件C语言描述第2版李学刚教学课件6-08堆排序1.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件6-08堆排序1.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2016数据结构Datastructure讲授：丁慧堆排序常州信息职业技术学院0203堆排序（1）定义：n个关键字序列kl,k2,…,kn称为堆，当且仅当该序列满足如下性质：   　①ki≤k2i且ki≤k2i+1(1≤i≤[n/2])或②ki≥k2i且ki≥k2i+1(1≤i≤[n/2])思考：若将此序列所存储的向量R[1...n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子结点的关键字。堆的任一子树亦是堆。1、堆三、链表的插入04关键字序列(12,35,15,47,40,18,68,56)12153

2、540186856475635124018476815堆排序满足堆的性质，因此该序列是堆关键字序列(56,12,35,15,40,18,47,68)不满足堆的性质，因此不是堆05堆排序（2）大根堆和小根堆根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆；根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者的堆称为大根堆。（3）堆的特点①大根堆（或小根堆）中，堆顶记录的关键字最大（或最小），因此在堆中很容易选取最大（或最小）关键字的记录。②堆的树形结构记录了大部分记录关键字之间的大小关系，因此可减少记录关键字的比较次数。06堆排序①初始状态：将R[1...n]

3、构造为初始堆；无序区包含所有记录R[1...n]，有序区为空2、用大根堆排序方法②交换：将锥顶记录R[1]和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1…n-1]和有序区R[n]，且满足R[1…n-1].keys≤R[n].key③重建堆:由于交换后新的锥顶记录R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。（1）第一趟排序：（2）第i趟排序：①排序前状态：无序区为R[1...n-(i-1)]，有序区为R[n-(i-1)+1...n]，无序区在第i-1趟已调整为堆②交换：将堆顶记录R[1]与无序区的最后一个记录R[n-i+1]交换，得到新的无序区R[

4、1…n-i]和有序区R[n-i+1...n]③重建堆:由于交换后新的锥顶记录R[1]可能违反堆性质，故应将当前无序区R[1..n-i]调整为堆。（3）重复进行第i趟的操作，直到无序区只有一个元素为止。07堆排序3、堆排序算法voidHeapSort(SeqListR){//对R[1...n]进行堆排序，用R[0]做暂存单元inti;BuildHeap(R);//对R[1...n]构建初始堆for(i=1;i

5、-(i-1)]=R[0];Heapify(R,1,n-i);//将新无序区R[1...n-i]调整为堆}}THANKS