采用堆结构的渐近最优整序算

《采用堆结构的渐近最优整序算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、198g年茫¨翔镦r子学与计算机采用堆结构的渐近最优整序算顾训穰诸宇章上海学技术大学计算机耳学系)摘耍结点，如果它右边帕任阿结点有儿子，则它本本文给出一个新的整序算法1主算采用墟结就有两个儿子．构，重新堆化用递归实现它不仅具有近最汪性定义殴二叉甜T是一个堆，T中任一能．而且将文献(1)和(5)巾的算法统一起来，拉为结点为窿昀子树足T的一个子堆(subheap)．运行时的特倒．定叉3T中任一结点处所附元素如果被取一前言疋，则该结点称为空铙结点．、理论上业已证明，任何比较整序至少需作三、算法／ogin1次比较’¨，砸Iogtnl

2、~nlog2n1。谩计思想这里的关键问题是需要对重一1．44n+logzn+1．32，下iJ以此作为比新堆化过程作出改进．考虑较整序的时间复杂性下界．l=2一／2～l，m=l，2，3，⋯⋯．六十年代由wil1]ans，Floyd提出的采用设当前堆的高度为．当把堆顶元素取走后，堆结构的HEAPSORT整序算法，以为了将这个当前堆重新堆化，只需注意到能移其数据缗构精致、简明、不需附加空间，且具人该空缺结点，充当新堆顶元素的必是其左右有较高的效率而被广泛采用．文献[5]对此作儿子中的一个．于是只需一次比较，就可使大了改进，使算法的

3、最环情况时间复杂性由者上升一层．令这个过程重复进行到第Ll^J2nlog：n0(n)降为4／3nlog3n+0(n)．层上的某一结点(即为空缺结点)处．如果能设法使复杂性的常数因子继续减小，并如果当前堆外的那个未整序的叶结点元素趋于1，则算法将得到进一步的改进，荠导致比该空缺结点的父结点元素不小，则将其移入渐近最优算法．这个空漱结点，并通过逐次与其父结点比较，二、定义使其上升到当前堆的某一合理位置}否则，递定义l设s是有线导的有限元素归地重新堆化以这个空缺结点为堆顶的当前子集，T是一棵高为瑚々二叉树，各结点由S中的堆．元素(

4、设为整数)端号。T三一一个堆(投大这一递归过程至多可一直连f亍至=1．此化)，当且仅当；时，将当前堆外的那个未整序目叶结点元素移(1)在以这棵二叉树上任何一个结点为入当前这个空歇结点，并至多作两次比较，就根；子树中，根的编号数不小它的所有子孙可把高度为I的这个当前子瑶重新堆化．的编号数．2．算法描述(2)这裸二叉树上有2个深度为h—l的(1)建立初始堆’l结点．procedureHEApFIFy(ij)；／／蒋数蚯元素深度为埘0第一f兰怍深度为h一1A(i)～A(j)建成难／／ifi不是一片叶且若i的儿子旨有一个比大的元素的

5、结点的左右儿子，且i泺度为h-0任一thenbegin令k是i的带有较大元素的儿子变换A(i)私A(k)；‘季刊1口88年月收到HEApFIFY(k，j)22截电子荦与计算机l■8●年第1lj弭begintempAL1J；end；ploc日qBUILDHE&P；ii~gAEt)一Llog(i-t)J；i}1．。^[D)建成堆／／￡ofiLn／2jstep-1until1doHEAPFIFYRE—UORD(i—J-I)(i，n)：AcjJ<--temp(2)重新堆化tend；r邮edLifeRE～UORD(i，j)将A【I)和

6、C2)交换-fh=Iend；then／／将高度为t的当前子堆重新准化，／四、复杂性分析beginA(i：÷Ai+1)；重新堆化过程是正确的，逸可对递归深度HEApFIFY(i，jJ施归纳证明．而整序算法的正确性则可通过对ende1sefor循环的执行次数施归纳证职．begin设在结点i到结点j范围内，以i为根的当Count‘-1：前堆的高度为h．则有：whileCountL：hJdo／／左右儿子作一引理递归过程RE—UORD的执行，需作次比辘-犬者上升一层的过程只进行到当前子比较次数堆的第2』层的茫结点处／／T(≤2Ih+I

7、og2^+1bgin令k是i的酱有较大元素的儿子；A[i]}A]i证明在将当前堆重新堆化时，从堆顶空i÷k：缺结点开始，其左右儿子通过一次比较，使太count~-count+者上升一层的过程只进行到第拍层的某结点end：处，共作拍次比较．然后把当前堆外的那个未j±A(II1)A【Li／2lj)整序的叶结元素A[j+1：和该空决结点的父then／，A[j÷】)在当前子笨中上升到集一台理位置／／结点元素作一发比较，在最坏情况下，或者beginAc．j÷A[j+1)A[j+1]上升至j茼堆’毪堆顶，共作z次比while)A[i)>

8、A(Lj／2do较，或者在以这夸空缺结点为堆顶，高度为begin交换A【i)与A[Li／2J)：(1一1)的”j冀予堆上递归地为A[j+1)寻i‘-iI2．找合理位置．：．i才下列递归方程：endendrl丁()．，=^l+{else／／递归地重新景化当前子差／／IT((1一：))begi