Mergeable Heaps• Binomial Heaps• Fibonacci HeapsData structures maintaining a dynamic set of items with keys, supporting InsertDeleteMin, Extract-MinUpdateUnionBinary heap for priority queueOps: insert, delete, extract-min (max)A balanced binary tree satisfying the heap property –Key of a node > key of its parentO(n) nodes, O(logn) height.Each op O(h)=O(logn)First Relaxation – leading to Binomial heapsA collection of trees (not necessarily binary).Heap property.Insert to smallest tree.No two trees of the same size. (To contain cost of extract-min).Example: Insert 5,4,3,2,1,7,8,9 a binomial tree →→Binomial tree.Bother theofroot theof child a becomes B one ofroot ,B twomerging :Bnode. single a :B1-k1-k1-kk0Properties:.|B|2|B| nodes.2 has B )2(iki)1,-B(k 1)-i 1,-B(k i)B(k,Bleft of i level Bleft of 1-i level :B of i level.B of i levelat nodes# i)B(k, (1)1-kkkk1-k1-kkn=÷÷øöççèæ=+=+=k. nodeevery of Degree .B,...,B :subtreesk has B ofRoot )4(.1)h(B)h(B ,0)h(B k.height has B )3(1-k0k1-kk0k≤+==Binomial Heaps: a set of binomial trees s.t.•Each tree satisfies the heap property.•No two roots have the same degree.logn. Hin trees#2n|H|:n1.or 0H heap in the B # niiiii≤Þ====åOperations:Min, Union, Insert, Extract-min, decrease, delete).H(H,n Unio then,H heap Binomial a x make :x)(H,Insert (3)binary.in |H| and |H| adding toAnalogous )H, Union(H(2)O(logn) trees.binomial theofrootsofmin Min(H) (1)112121=logn.deg(x) :O(logn) ).H(H, UnionH. from x Remove trees.binomialmember as with themH heapnew a create and x from x of subtrees Cut the key. minimumroot with thebeLet x Min(H)-Extract (4)11≤min-Extract "."- tok(x) Decrease (x)Deletet (6) O(logn) restored. isproperty heap until tree theup-Bubble :e(x)(5)Decreas∞General idea of relaxation – delay work as much as possible.First relaxation – Delay enforcement until an extract-min. op; consolidate the work after an extract-min.Defn Fibonacci heap•A collection of unordered trees.•Each satisfying the heap property.•Roots are linked in a circular list.•A pointer to the root with the minimum key.A nice property to maintain --Heap size be exponential in max. degree of nodes.Implications:•Max. degree of any node = O(logn)•O(logn) trees in the heap, if no two roots have the same degree.Primitives–O(1) per op, including cost for maintaining min(H).Create(x) -- A new node x is created.Remove(x) – Node x, a singleton, is removed from the F-heap.Cut(x) •x cannot be a root. •The subtree rooted at x is cut from parent(x) and become a new tree.•When – delete or update, or a second child of x is cut-off from x (cascade-cut).Link(x,y)•x and y are roots.•degree(x)=degree(y).•key(x) key(y).•When– only applied during consolidation.Mark(x)•x cannot be a root.•When – after first cut happens to any child of x.≥Policy1. Heap property.2. (Link policy) Two roots are linked only if their degrees are the same.3. (Cut policy) After becoming a non-root, a node can have at most one child cut off. (2ndcut-off causes the node itself to be cut off from its parent and become a root.)4. Consolidate only after an extract-min is performed.Lemma 1Policy.on dependnot does proof :Remark0)()(links#cuts#)()(insertions#links#cuts#)(1 )(insert1)(link1)(cut.in trees#:)(:Prinitially trees# where ,insertions#cuts#links#0000≥Φ=Φ+−Φ−Φ=∆Φ+−=∆Φ=∆Φ=∆ΦÞ−=∆ΦÞ=∆ΦÞ=Φ=++≤åNNiHHHHiiiiHHoofnnLemma 2cuts. actual#cuts-cascade# ≤cuts. actual#cuts-cascade#)0)0(( .0)()0()(cuts-cascadecuts-# actual#)(.1)(cut cascade.1)(cut actual:stepth op. primitive a ofn applicatioan -- step Each timecut)-cascade2 marked;1 roots;for 0 0;initially is )((lost. has children #)( where,)(:)(:Pr≤Þ=Φ≥Φ=Φ−Φ=∆Φ≤∆Φ=∆ΦÞ−≤∆ΦÞ≤∆ΦÞ→⇔==ΦååTTiiiivlostvvlostvlostHoofivLemma 3cuts) actual#O(1cost amortized0:Reinsert#cuts actual#4cuts#2links#cuts#cuts actual2#cuts#cuts. actual#cuts-cascade:#2 Lemma .insert#cuts#links#:1 Lemma:Prinitially trees# where,insertions#cuts actual#4links#cuts#000000+=Þ=++≤+≤+≤Þ≤++≤=++≤+nmarknnnoofnnLemma 4. at time of degree :)(deg. size of heap-Fan in degree of node a :empty.)initially iswhich heap-Fan of ionsconfigurat possible allover min (. degree of node aat rooted subtree ina nodes# min:)(:Prpolicies.Link andCut of econsequenc a :Re.# where1,log2 degree has nodeAny twwnkwkkGoofmarkHnnt====+≤degree). same thehave they ifonly linked are nodes (two 1)(deg)(deg So,me.at that ti ofchildren were,..., since ,1)(deg..... time to of child a remains and tolinked wasat which time: . at time ofchildren :,...,.)(deg Supposeop. primitive one ofn applicatio :step One11211−≥=−≥≤<<<≤=−iwvwvviwtttttwwvtttwvvkwiiitititkiikt.111)1(...)3()2()( So,.111)1(...)3()2(| at time at rooted Subtree|)2( | tat time at rooted Subtree|.21)(deg)(deg So,policy)Cut -3 Inv.(. from offcut been have would elseoff,cut child onemost at has , to timeFrom+++++−+−≥+++++−+−≥−≥−≥−≥GkGkGkGGkGkGtwiGvivvwvvttiititiiii.log)2()().2( 111)3(...)1()( 111)1(...)3()2()(.1,...,0),2()( assumey Inductivel.2)1(,1)0(.1)1(...)()2(.215,)().2()1()(,1)2()1(:sequence Fibonacci2nkkFkGnkFFkFkFGkGkGkGkiiFiGGGFkFkFkFkFkFkFFFkkαααα≤Þ≥+≥≥+=+++++−+≥+++++−+−≥−=+≥==+++=++=≥−+−===−Lemma 5.log2 node a of reedeg4 Lemma:Prdegree. same theof are roots twono if trees1log2 thanmore no has size of heap FibonacciA noofnn≤Þ+Amortized cost of a data structure operation ))(ˆ( n).cuts actual# O(total n links # total cuts # total)(Thenops of sequence a :,..., todue cuts actual#1:)(ˆmin.-extractdelete, assuch operation structure data a :11n1åå===+=++≤+=niiniicOccσσσσσσσExtract-min•The root with the minimum key is extracted.•The subtrees of this root become new trees.•Consolidation work – merge trees using link op until no two roots have the same degree.Amortized cost = O(log |H|).Delete(x)•cut(x), then cut (y) for each child y of x.•Remove(x).Amortized cost = O(deg(x))=O(log|H|).Decrease(x)Update on x and if heap property is violated, then cut(x). Amortized cost =