资源描述：
《最优堆排序算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第21卷第5期小型微型计算机系统Vol.21No.52000年5月MINI-MICROSYSTEMMay2000文章编号:1000-1220(2000)05-0472-03最优堆排序算法王晓东(福州大学计算机科学与技术系福州350002)摘要:本文讨论了堆的若干性质,提出对堆排序算法的改进.改进后的堆排序算法是一个最优排序算法,在最坏情况下需要nlogn+n3(n)+O(n)次元素比较和nlogn+O(n)次元素移动.关键词:堆;算法;计算复杂性分类号:TP301文献标识码:A1引言的选择有较大的灵活性
2、.f(h)的不同选择,对算法的效率有很大的影响.堆是表示有序集的一棵完全二叉树T,且满足如下的堆另一个值得注意的问题是,在这个重建堆过程中,元素的性质,即T中每一个结点中元素的键值至多和它父结点中元比较与元素的移动是同时进行的.这样就会产生一些不必要素键值一样大.因此堆中最大元素就存放在根结点中.如果用的元素移动.如图1所示.一个数组A〔1..n〕来实现堆,则可将堆中元素按自顶向下,从左到右的顺序依次存储在数组元素A〔1〕,A〔2〕,⋯,A〔n〕中.在一般情况下,堆中元素A〔i〕的左儿子结点元素为A〔2i
3、〕,右儿子结点元素为A〔2i+1〕,父结点元素为A[[i/2]].此时,堆性质可表述为:A[[i/2]]≥A[i],2≤i≤n60年代源于Williams的堆排序算法,首次提出堆的这种结构,用O(n)时间建立初始堆,然后不断地交换堆顶与堆底元素,并重新建堆,最终将所有元素整好序.图1元素的不必要移动容易看出,在堆排序算法中,主要计算量在于重建堆的过基于以上考虑,本文利用堆结构的一些优良性质,对重建程.而重建堆算法的效率是由堆中元素的比较次数以及堆中堆算法提出两点改进:元素的移动次数来衡量的.常用的重建堆算
4、法Heapify〔1,2〕使(1)将元素的比较与元素的移动分离,避免元素不必要的根结点元素沿着某条路径向下渗,每下渗一层需作2次比较:移动.父结点的左、右儿子结点元素作1次比较,大者再与父结点元(2)对f(h)的选择进行优化,迅速地找到待排序叶结点素作1次比较,这个过程一直重复到父结点元素不小于其儿的正确插入位置.子结点元素.因此,在最坏情况下需要2nlogn+O(n)次比较和nlogn+O(n)次元素移动.2堆的若干重要性质实际上我们可以在一个更一般的框架下讨论重建堆算A〔1..n〕是一个堆.法.定理1
5、:设A〔k〕是堆A中任一结点.从堆顶A〔1〕到A设当前堆的高度为h,当把堆顶元素取走后,产生了一个〔k〕确定了一条唯一的路径,且在此路径上的诸元素A〔1〕,A空缺结点.为了将这个当前堆重新堆化,只需注意到能移入该〔i1〕,⋯,A〔k〕已从大到小整好序.空缺结点充当新堆顶元素的必是其左右儿子中的大者(称为证明:显而易见.长子).于是只需一次比较就可使长子上升一层.令这个过程若对数组A的每一下标i(1≤i≤n)作一标记m(i)使得重复进行到f(h)层上的某一结点处.如果当前堆外的那个未排序叶结点元素比该结点的
6、父结点元素不小,则将其移入这0,i=2j,j=1,2⋯,n/2;m(i)=个空缺结点,并通过逐次与其父结点比较,使其上升到当前堆1,i=2j-1,j=1,2⋯,n/2;的某一合理位置.否则,递归地重新堆化以这个空缺结点为堆则堆中任一从根结点A〔1〕到结点A〔k〕的路径可用标记顶的当前子堆.序列{m(1),⋯,m(k)}唯一表示.我们称这种路径表示方法为在这个重新堆化的过程中,沿长子路径下降的层数f(h)根节点A〔1〕到堆中任一结点A〔k〕的路径标记.收稿日期:1999-05-26基金项目:福建省自然科学基
7、金资助项目作者简介:王晓东,教授,研究领域为数据结构,算法设计与分析.5期王晓东等:最优堆排序算法473定理2:对任一正整数k(1≤k≤n),若k的二进制表示A〔1〕到结点A〔k〕的路径上A〔m〕处插入.否则,递归地查找为:A〔n〕的合理插入位置.一旦确定了A〔n〕的合理插入位置m,[logk]就可用算法insert(m,n)用最少的移动次数,将A〔n〕插入到i,bk=bi(k)2i(k)∈{0,1}所确定的合理位置上.i=0则序列{b[logk](k),⋯,b0(k)}为堆中从根A〔1〕到结点Apro
8、cedureinsert(position,bottom:integer);〔k〕的路径标记.反之亦然.vari,current:integer;temp:real;证明:见〔3〕.begintemp:=a〔1〕;由定理2和定理3可知,在从根结点A〔1〕到结点A〔k〕ifposition=1thencurrent:=position的路径上依路长从大到小排列的[logk]+1个元素中,第i个else元素(0≤i≤[logk])
