Mergeable Heaps Binomial Heaps Fibonacci Heaps Data structures maintaining a dynamic set of items with keys supporting Insert Delete Min Extract Min Update Union Binary heap for priority queue Ops insert delete extract min max A balanced binary tree satisfying the heap property Key of a node key of its parent O n nodes O logn height Each op O h O logn First Relaxation leading to Binomial heaps A 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 B0 a single node Bk merging two Bk 1 root of one Bk 1 becomes a child of the root of the other Bk 1 Properties 1 B k i nodes at level i of Bn level i of Bk level i 1 of left Bk 1 level i of left Bk 1 k B k i B k 1 i 1 B k 1 i i k 2 Bk has 2 nodes Bk 2 Bk 1 3 Bk has height k h B0 0 h Bk h Bk 1 1 4 Root of Bk has k subtrees B0 Bk 1 Degree of every node k Binomial Heaps a set of binomial trees s t Each tree satisfies the heap property No two roots have the same degree n i Bi in the heap H 0 or 1 n H n i 2i i trees in H logn Operations Min Union Insert Extract min decrease delete 1 Min H min of roots of the binomial trees O logn 2 Union H1 H 2 Analogous to adding H1 and H 2 in binary 3 Insert H x make x a Binomial heap H1 then Union H H1 4 Extract Min H Let x be the root with minimum key Cut the subtrees of x from x and create a new heap H1 with them as member binomial trees Remove x from H Union H H1 O logn deg x logn 5 Decrease x Bubble up the tree until heap property is restored O logn 6 Deletet x Decrease k x to Extract min General idea of relaxation delay work as much as possible First relaxation Delay enforcement until an extractmin 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 cutoff 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 Policy 1 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 2nd cut 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 1 links cuts n0 insertions where n0 trees initially Pr oof H trees in H cut i 1 link i 1 insert i 1 i cuts links insertions i H N H 0 cuts links H 0 H N 0 Remark proof does not dependon Policy Lemma 2 cascade cuts actual cuts Pr oof H lost v where lost v children v has lost v lost v is initially 0 0 for roots 1 marked 2 cascade cut Each time step an application of a primitive op ith step actual cut i 1 cascade cut i 1 i actual cuts cascade cuts i T 0 T 0 0 0 cascade cuts actual cuts Lemma 3 cuts links 4 actual cuts insertions n0 where n0 trees initially Pr oof Lemma 1 links cuts n0 insert Lemma 2 cascade cuts actual cuts cuts 2 actual cuts cuts links 2 cuts n0 4 actual cuts insert n0 Re mark n0 0 amortized cost O 1 actual cuts Lemma 4 Any node has degree 2 log n 1 where n H Re mark a consequence of Cut and Link policies Pr oof G k min nodes ina subtree rooted at a node of degree k min over all possible configurations of an F heap which is initially empty w a node of degree k in an F heap of size n deg t w degree of w at time t One step application of one primitive op Suppose deg t w k v1 vk children of w at time t ti t time at which vi was linked to w and remains a child of w to time t t1 t 2 t k t deg ti w i 1 since v1 vi 1 were children of w at that time So deg ti vi deg ti w i 1 two nodes are linked only if they have the same degree From time ti to t vi has at most one child cut off else vi would have been cut off from w Inv 3 Cut policy So deg t vi deg ti vi 1 i 2 Subtree rooted at vi at time t G i 2 Subtree rooted at w at time t G k 2 G k 3 G 1 1 1 1 So G k G k 2 G k 3 G 1 1 1 1 Fibonacci sequence F 1 F 2 1 F k F k 1 F k 2 5 1 F k 2 F k 2 F k F 1 1 k 2 G 0 1 G 1 2 Inductively assume G i F i 2 i 0 k 1 G k G k 2 G k 3 G 1 1 1 1 F k F k 1 F 3 1 1 1 F k 2 n G k F k 2 k k log n Lemma 5 A Fibonacci heap of size n has no more than 2 log n 1 trees if no two roots are of the same degree Pr oof Lemma 4 deg ree of a node 2 log n Amortized cost of a data structure operation a data structure operation such as delete extract min c 1 actual cuts due to 1 n a sequence of ops Then n c total cuts total links n i 1 i O total actual cuts n n O c i i 1 Extract …
View Full Document
Unlocking...