课程
operationsinStep3isthenumberofrootswestartwith,whichislessthanri 1+D(n),minusthenumberofrootsweendupwith,whichisri.AfterStep3,allrootshavedifferentdegrees,whichimpliesri≤D(n)+1.Itfollowsthattheactualcostforallfourstepsisci≤2+ri 1+2D(n) ri.ThepotentialchangeisΦi Φi 1=ri ri 1.Theamortizedcostistherefore
ai
=ci+Φi Φi 1≤2D(n)+2.




delete 4
WewillprovenexttimethatthemaximumpossibledegreeisatmostlogarithmicinthesizeoftheFibonacciheap,D(n)<2log2(n+1).Thisimpliesthatdeletingtheminimumhaslogarithmicamortizedcost.
Decreasekeyanddelete.Besidesdeletemin,wealsohaveoperationsthatdeleteanarbitraryitemandthatde-creasethekeyofanitem.Bothchangethestructureoftheheap-orderedtreesandarethereasonwhyaFibonacciheapisnotacollectionofbinomialtreesbutofmoregen-eralheap-orderedtrees.Thedecreasekeyoperationre-placestheitemwithkeyxstoredinthenodeνbyx ,inwhich isanon-negativerealnumber.Wewillseethatthiscanbedonemoreef cientlythantodeletexandtoinsertx .Wedecreasethekeyinfoursteps.StepStepStepStep
1.Unlinkthetreerootedatν.2.Decreasethekeyinνby .
3.Addνtotherootcycleandpossiblyupdatethepointertotheminimumkey.4.Docascadingcuts.
Figure47:AFibonacciheapinitiallyconsistingofthreebino-mialtreesmodi edbyadecreasekeyandadeleteoperation.
Cascadingcuts.Letνbeanodethatbecomesthechildofanothernodeattimet.Wemarkνwhenitlosesits rstchildaftertimet.Thenweunmarkν,unlinkit,andaddittotheroot-cyclewhenitlosesitssecondchildthereafter.Wecallthisoperationacut,anditmaycascadebecauseonecutcancauseanother,andsoon.Figure48illus-tratestheeffectofcascadinginaheap-orderedtreewithtwomarkednodes.The rststepdecreaseskey10to7,andthesecondstepcuts rstnode5andthennode





4.
Figure48:Theeffectofcascadingafterdecreasing10to7.Markednodesareshaded.
Wewillexplaincascadingcutsshortly,afterexplainingthefourstepswetaketodeleteanodeν.Beforewedeleteanodeν,wecheckwhetherν=min,andifitisthenwedeletetheminimumasexplainedabove.Assumethereforethatν=min.StepStepStepStep
1.Unlinkthetreerootedatν.
2.Mergetheroot-cyclewiththecycleofν’schil-dren.
3.Disposeofν.4.Docascadingcuts.
Summaryanalysis.Asmentionedearlier,wewillproveD(n)<2log2(n+1)nexttime.Assumingthisbound,weareabletocomputetheamortizedcostofalloperations.TheactualcostofSteps4indecreasekeyandindeleteisthenumberofcuts,ci.Thepotentialchangesbecausetherearecinewrootsandcifewermarkednodes.Also,thelastcutmayintroduceanewmark.Thus
Φi Φi 1
=ri+2mi ri 1 2mi 1≤ci 2ci+2= ci+2.
Theamortizedcostisthereforeai=ci+Φi Φi 1≤ci (2 ci)=2.The rstthreestepsofadecreasekeyoperationtakeonlyaconstantamountofactualtimeandincreasethepotentialbyatmostaconstantamount.Itfollowsthattheamortizedcostofdecreasekey,including
Figure47illustratestheeffectofdecreasingakeyandofdeletinganode.Bothoperationscreatetreesthatarenotbinomial,andweusecascadingcutstomakesurethattheshapesofthesetreesarenotverydifferentfromtheshapesofbinomialtrees.









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 Heapslecture ppt for Fibonacci Heaps隐藏>> Outline CS570: Introduction to Algorithms Lecture 14 Fall 1998 University of Southern ...
2. Heap Structures 9 Min-max heaps – Deaps – Leftist heaps –Binomial heaps – Fibonacci heaps – Skew heaps - Lazy-binomial heaps. 3. Search ...
Min-max heaps – Deaps – Leftist heaps –Binomial heaps – Fibonacci heaps – Skew heaps-_电脑基础知识_IT/计算机_专业资料 暂无评价
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 Executable Description in CHR Jon Sneyers, Tom Schrijvers, Bart Demoen Report CW 429, November 2005 ...
高级数据结构 ——Fibonacci堆 Fibonacci Heaps Fibonacci Heaps Actual O(1) Amortized O(1) O(log n) O(1) O(log高级数据结构 ——Fibonacci堆 Fibonacci ...
Priority Queues Fibonacci Heaps Heaps Operation make-heap insert These lecture slides are adapted from CLRS, Chapter 20. find-min delete-min union ...
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...
热门文档