文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 资格考试/认证 > 从业资格考试 > fibonacci heaps
侵权投诉

fibonacci heaps

课程

fibonacci heaps

operation.SinceΦ0=0andΦi≥0foralli,theactualcostislessthantheamortizedcost:

n i=1

ci≤

n i=1

ai=rn+2mn+

n i=1

ci.

Figure45:TheFibonacciheaprepresentationofthe rstcollec-tionofheap-orderedtreesinFigure44.

Forsomeoftheoperations,itisfairlyeasytocompute

theamortizedcost.Wegettheminimumbyreturningthekeyinthemarkedroot.Thisoperationdoesnotchangethepotentialanditsamortizedandactualcostisai=ci=1.WemeldtwoFibonacciheapsH1andH2by rstmergingthetworootcirclesandsecondadjustingthepointertotheminimumkey.Wehave

ri(H1)=ri 1(H1)+ri 1(H2),mi(H1)=mi 1(H1)+mi 1(H2),

whichimpliesthatthereisnochangeinpotential.Theamortizedandactualcostisthereforeai=ci=1.WeinsertakeyintoaFibonacciheapby rstcreatinganewFibonacciheapthatstoresonlythenewkeyandsecondmeldingthetwoheaps.WehaveonemorenodeintherootcyclesothechangeinpotentialisΦi Φi 1=1.Theamortizedcostisthereforeai=ci+1=2.Deletemin.Nextweconsiderthesomewhatmorein-volvedoperationofdeletingtheminimumkey,whichisdoneinfoursteps:StepStep

1.Removethenodewithminimumkeyfromtherootcycle.

2.Mergetherootcyclewiththecycleofchildrenoftheremovednode.

3.Aslongastherearetworootswiththesamedegreelinkthem.

4.Recomputethepointertotheminimumkey.

markthenode.Therootsoftheheap-orderedtreesaredoubly-linkedinacycle,andthereisanexplicitpointertotherootthatstorestheitemwiththeminimumkey.Figure46illustratesafewbasicoperationsthatwecanperformonaFibonacciheap.Giventwoheap-orderedtrees,we

unlinking

linking

fibonacci heaps

fibonacci heaps

fibonacci heaps

fibonacci heaps

merging

Figure46:Cartoonsforlinkingtwotrees,unlinkingatree,andmergingtwocycles.

linkthembymakingtherootwiththebiggerkeythechildoftheotherroot.Tounlinkaheap-orderedtreeorsubtree,weremoveitsrootfromadoubly-linkedcycle.Finally,tomergetwocycles,wecutbothopenandconnectthemattheirends.Anyoneofthesethreeoperationstakesonlyconstanttime.

Potentialfunction.AFibonacciheapsupportsavari-etyofoperations,includingthestandardonesforpriorityqueues.Weuseapotentialfunctiontoanalyzetheiramor-tizedcostappliedtoaninitiallyemptyFibonacciheap.Lettingribethenumberofrootsintherootcycleandmithenumberofmarkednodes,thepotentialafterthei-thoperationisΦi=ri+2mi.WhenwedealwithacollectionofFibonacciheapswede neitspotentialasthesumofindividualpotentials.TheinitialFibonacciheapisempty,soΦ0=0.Asusualweletcibetheactualcostandai=ci+Φi Φi 1theamortizedcostofthei-th

StepStep

ForStep3,weuseapointerarrayR.Initially,R[i]=NULLforeachi.Foreachroot intherootcycleweexecutethefollowingiteration.

i= →degree;

whileR[i]=NULLdo

=R[i];R[i]=NULL; =LINK( , );i++endwhile;R[i]= .

Toanalyzetheamortizedcostfordeletingtheminimum,letD(n)bethemaximumpossibledegreeofanynodeinaFibonacciheapofnnodes.Thenumberoflinking

上一页第2页

你可能喜欢

热门文档

相关文档

  • Are Fibonacci heaps optimal

    ed Fibonacci heap which does, and so is optimal under our assumptions. 4 January, 1994 Are Fibonacci Heaps Optimal? Diab Abuaiadh and Jeffrey H. ...

  • lecture ppt for Fibonacci Heaps

    lecture ppt for Fibonacci Heapslecture ppt for Fibonacci Heaps隐藏>> Outline CS570: Introduction to Algorithms Lecture 14 Fall 1998 University of Southern ...

  • ...Fibonacci heaps – Skew heaps-

    2. Heap Structures 9 Min-max heaps – Deaps – Leftist heaps –Binomial heaps – Fibonacci heaps – Skew heaps - Lazy-binomial heaps. 3. Search ...

  • ...heaps – Fibonacci heaps – Skew heaps-

    Min-max heaps – Deaps – Leftist heaps –Binomial heaps – Fibonacci heaps – Skew heaps-_电脑基础知识_IT/计算机_专业资料 暂无评价

  • Dijkstra’s algorithm with Fibonacci heaps An execu...

    Dijkstra’s algorithm with Fibonacci heaps An executable description Abstract. We construct a readable, compact and efficient implementation of Dijkstra’s ...

  • Dijkstra’s algorithm with Fibonacci heaps An execu...

    Dijkstra’s Algorithm with Fibonacci Heaps: An Executable Description in CHR Jon Sneyers, Tom Schrijvers, Bart Demoen Report CW 429, November 2005 ...

  • 8_Fibonacci堆

    高级数据结构 ——Fibonacci堆 Fibonacci Heaps Fibonacci Heaps Actual O(1) Amortized O(1) O(log n) O(1) O(log高级数据结构 ——Fibonacci堆 Fibonacci ...

  • fibonacci-4up

    Priority Queues Fibonacci Heaps Heaps Operation make-heap insert These lecture slides are adapted from CLRS, Chapter 20. find-min delete-min union ...

  • fibonacci-heap

    Priority Queues Performance Cost Summary Fibonacci Heaps Operation make-heap is-empty insert delete-min decrease-key delete union Linked List 1 1 1 n n...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email