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

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

1、2016数据结构Datastructure讲授：丁慧堆排序常州信息职业技术学院02三、链表的插入08②否则用large指示两个孩子结点中关键字较大者的下标，将R[low]与R[large]交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。堆排序4、重建堆方法——筛选法设当前无序区为R[low...high],R[low]的左、右子树均已是堆，只有R[low]可能违反堆性质。①若R[low].key不小于R[low]的左右孩子

2、结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；三、链表的插入09123556401827815堆排序关键字序列R[1…8]=(12,56,35,15,40,18,27,8)largelow1256lowlarge124010堆排序5、重建堆的算法：voidHeapify(SeqListR,intlow,inthigh){//将R[low...high]调整为大根堆intlarge;//large指向调整结点的左右孩子结点中关键字较大者R[0]=R[low];//暂存调整结点for(large=2*low;large<=high;large*=2){//R[l

3、ow]是当前调整结点，先让large指向R[low]的左孩子if(large=R[large].key)//temp始终对应R[low]break;//结束调整R[low]=R[large];//相当于交换了R[low]和R[large]low=large;//使low指向新的调整结点，相当于已筛到large的位置}R[low]=R[0];}11voidBuildHeap(SeqListR){//将初始文件R[1...n]构造成大根堆inti;for(i=n/

4、2;i>0;i--)Heapify(R,i,n);//将R[1...n]调整为大根堆}堆排序6、构建初始堆的方法要将初始文件R[l...n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。　　依次将以序号为[n/2],[n/2]-1,…,1的非叶子结点作为根的子树都调整为堆(调用重建堆)即可。7、构建初始堆的算法12堆排序8、算法分析（1）平均时间复杂度为O(nlgn)（2）辅助空间为O(1),为就地排序（3）堆排序时不稳定的排序方法THANKS