Understanding Fibonacci Heaps and Operations

Fibonacci heaps are a type of data structure that supports efficient operations such as insertion, deletion, and finding the minimum key. They consist of heap-ordered trees rooted but unordered. Each node points to its parent, children, and siblings. The potential function and unordered binomial trees are also part of the structure. The cost of operations in Fibonacci heaps is amortized, making them suitable for dynamic sets.

• Fibonacci Heap
• Data Structure
• Heap Operations
• Amortized Cost
• Potential Function

maryjayne Follow

Uploaded on Sep 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Fibonacci Heap

2. Binary heap (worst-case) Binomial heap (worst-case) Fibonacci heap (amortized) Procedure (1) (1) (1) MAKE-HEAP (lg n) (1) INSERT O(lg n) (1) (1) MINIMUM O(lg n) (lg n) (lg n) EXTRACT-MIN O(lg n) (n) (1) UNION O(lg n) (lg n) (lg n) (1) DECREASE-KEY (lg n) (lg n) DELETE O(lg n) p2.

3. H.min (a) 23 7 3 17 24 26 30 52 18 38 46 35 39 41 H.min (b) 23 7 3 17 24 26 46 30 52 18 38 35 39 41 p3.

4. H.min (a) 23 7 3 17 24 26 30 52 18 38 46 35 39 41 Insert key 21 H.min 21 (b) 23 7 3 17 24 26 30 52 18 38 46 35 39 41 p4.

5. Fibonacci Heaps: A collection of heap-ordered trees. trees: rooted but unordered Each node x: x.p points to its parent x.child points to any one of its children children of x are linked together in a circular doubly linked list x.Left, x.right: points to its left and right siblings. x.degree: number of children in the child list of x x.mark: indicate whether node x has lost a child since the last time x was mode the child of another node H.min: points to the root of the tree containing a minimum key H.n: number of nodes in H p5.

6. Potential function: (H) = t(H) + 2m(H) # of marked nodes in H # of trees in the rooted list of H Fibonacci heap D(n): upper bound on the max degree of any node in an n-node Fibonacci heap p6.

7. Unordered binomial tree: U0: a single node Uk: consists of 2 unordered binomial trees Uk-1 for which the root of one is made into any child of the root of the other Make-Heap, Insert, Minimum, Extract-Min & Union. Fibonacci heap unordered binomial trees. Make-Heap, Make-Fib-Heap(H): Allocate and return the Fibonacci heap object H with H.n=0 and H.min=nil t(H)=0 , m(H)=0 so (H)=0 The amortized cost of Make-Fib-Heap is equal to its O(1) actual cost. p7.

8. Fib-Heap-Insert(H, x) 1. x.degree = 0 2. x.p = NIL 3. x.child = NIL 4. x.mark = FALSE 5. if H.min == NIL 6. create a root list for H containing just x 7. H.min = x 8. else insert x into H s root list 9. if x.key < H.min.key 10. H.min = x 11. H.n = H.n +1 Actual cost: O(1); Amortized cost: O(1) + 1 p8.

9. Finding the minimum node: min[H] O(1) Amortized cost O(1) is not changed Uniting 2 Fibonacci heaps: Fib-Heap-Union(H1, H2) 1. H = Make-Fib-Heap( ) 2. H.min = H1.min 3. concatenate the root list of H2 with the root list of H 4. if (H1.min == NIL) or (H2.min NIL and H2.min.key<H1.min.key) 5. H.min = H2.min 6. H.n = H1.n + H2.n 7. return H p9.

10. (H) - ((H1)+(H2)) = (t(H)+2m(H)) ((t(H1)+2m(H1)) + (t(H2)+2m(H2))) = 0 t(H) = t(H1) + t(H2) , m(H) = m(H1) + m(H2) Thus the amortized cost of Fib-Heap-Union is therefore O(1) actual cost p10.

11. Extracting the minimum node: Fib-Heap-Extract-Min(H) 1. z = H.min 2. if z NIL 3. for each child x of z 4. do { add x to the root list of H 5. x.p = NIL } 6. remove z from the root list of H 7. if z == z.right 8. H. min = NIL 9. else H.min = z.right 10. Consolidate(H) 11. H.n = H.n 1 12. return z p11.

12. Fib-Heap-Link(H, y, x) {1. remove y from the root list of H; 2. make y a child of x; x.degree =x.degree+1; 3. y.mark = FALSE; } Consolidate(H) 1. let A[0..D(H.n)] be a new array 2. for i = 0 to D(n[H]) do A[i]=NIL 3. for each node w in the root list of H 4. do { x = w ; d = x.degree; 5. while A[d] NIL 6. do { y = A[d] 7. 8. 9. 10. A[d] = x; } 11. H.min = NIL 12. for i = 0 to D(H.n) do 13. if A[i] NIL 14. if H.min==NIL 15. create a root list for H containing just A[i]; H.min =A[i]; 16.else insert A[i] into H s root list 17. if A[i].key < H.min.key H.min = A[i] if x.key > y.key exchange x y Fib-Heap-Link(H, y, x) A[d] = NIL ; d = d+1; } p12.

13. H.min 21 (a) 23 7 3 17 24 26 30 52 18 38 46 35 39 41 H.min 21 17 18 38 (b) 23 7 24 52 39 41 26 30 46 35 p13.

14. 0 1 2 3 4 A w,x 21 17 18 38 (c) 23 7 24 52 39 41 26 30 46 35 0 1 2 3 4 A w,x 21 17 18 38 (d) 23 7 24 52 39 41 26 30 46 35 p14.

15. 0 1 2 3 4 A w,x 21 17 18 38 (e) 23 7 24 52 39 41 26 30 46 35 0 1 2 3 4 A x 7 17 18 38 (f) 24 21 52 w 23 39 41 26 30 46 35 p15.

16. 0 1 2 3 4 A x 7 38 (g) 24 21 18 52 w 23 17 39 41 26 46 30 35 0 1 2 3 4 A x 7 38 21 18 52 (h) w 23 24 17 39 41 26 46 30 35 p16.

17. 0 1 2 3 4 A w, x 7 38 21 18 52 (i) 23 24 17 39 41 26 46 30 0 1 2 3 4 35 A w, x 7 38 21 18 52 (j) 23 24 17 39 41 26 46 30 35 p17.

18. 0 1 2 3 4 A w, x 7 18 38 (k) 23 24 21 39 17 41 26 46 30 52 35 0 1 2 3 4 A w, x 7 18 38 (l) 23 24 21 39 17 41 26 46 30 52 35 p18.

19. H.min 7 18 38 (m) 23 24 21 39 17 41 26 46 30 52 35 p19.

20. Decreasing a key and deleting a node: do not preserve the property that all trees in the Fibonacci heap are unordered binomial trees. Fib-Heap-Decrease-key(H, x, k) 1. if k>x.key 2. error new key is greater than current key 3. x.key = k 4. y x.p 5. if y NIL and x.key< y.key 6. { CUT(H, x, y) 7. CASCADING-CUT(H, y) } 8. if x.key< H.min.key 9. H.min = x p20.

21. CUT(H, x, y) 1. remove x from the child list of y, decrease y.degree 2. add x to the root list of H 3. x.p = NIL 4. x.mark = FALSE Fib-Heap-Delete(H, x) { Fib-Heap-Decrease-key(H, x, - ) Fib-Heap-Extract-Min(H) } CASCADING-CUT(H, y) 1. z y.p 2. if z NIL 3. if y.mark == FALSE 4. y.mark= TRUE 5. else CUT(H, y, z) 6. CASCADING-CUT(H, z) p21.

22. H.min 7 18 38 (a) 23 24 21 39 17 41 26 46 30 52 35 H.min 7 15 18 38 (b) 23 24 21 39 17 41 26 30 52 35 p22.

23. H.min 7 15 5 18 38 (c) 23 24 21 39 17 41 30 26 52 H.min 7 15 5 18 38 26 (d) 23 24 21 39 17 41 30 52 p23.

24. H.min 7 15 5 18 38 24 26 (e) 23 17 21 39 41 30 52 p24.

25. Analysis of Decrease-key: Actual cost : O(c) suppose CASCADING-CUT is called c times Each recursive call of CASCADING-CUT except for the last one, cuts a marked node and clears the mark bit. After Decrease-key, there are at most t(H)+c trees, and at most m(H)-c+2 marked nodes. Last call of CASCADING-CUT may have marked a node Thus; the potential change is : [t(H)+c+2(m(H)-c+2)] - [t(H)+2m(H)] = 4-c Amortized cost: O(c)+4-c = O(1) By scaling up the units of potential to dominate the constant hidden in O(c) p25.

26. Analysis of Fib-Heap-Extract-Min: H : n-node Fib-Heap Actual cost : O(D(n)) : for-loop in Fib-Heap-Extract-Min D(n)+t(H)-1 : size of the root list Total actual cost: O(D(n))+t(H) Potential before extracting : t(H)+2m(H) Potential after extracting : D(n)+1+2m(H) At most D(n)+1 nodes remain on the list and no nodes become marked Thus the amortized cost is at most: O(D(n))+t(H)+[(D(n)+1+2m(H)) (t(H)+2m(H))] = O(D(n)+t(H)-t(H)) = O(D(n)) p26.

27. Bounding the maximum degree: + (1 5)/2 Goal : D(n) log n , = Let size(x) be the number of nodes, including x itself, in the subtree rooted at x p27.

28. Lemma 1 x : any node in a Fibonacci heap and x.degree=k y1, , yk : children of x in the order in which they were linked to x. (from the earliest to the latest) Then, y1.degree 0 and yi.degree i-2 for i=2,3, ,k Pf: Clearly, y1.degree 0 For i 2, note that when yi was linked to x, all of y1, , yi-1 were children of x, so we MUST have had x.degree i-1. Node yi is linked to x only if x.degree = yi.degree, thus yi.degree i-1 at that time. Since then, node yi has lost at most ONE child, since it would have been cut from x if it had lost two children. We conclude that yi.degree i-2 x yk y1 y2 p28.

29. Fibonacci number: 0 if k F 1 if k F + = = 0 1 2 = k k 2 F if k k 1 Lemma 2: For all integer k 0, pf: By induction on k k=0, F2=F1+F0=1 = 1+F0 Suppose k 1 F k + = k 2 F 1 F + i i 0 = k 1 + = 1 F + i i 0 = F k 1 k = + = + + = + k 2 F F F 1 F 1 F + k 1 + k k i i i 0 = i 0 = k + = + k 2 F , (1 5)/2 1.618 p29.

30. Lemma 3: x: any node in a Fibonacci heap, and let k=x.degree Then, size(x) Fk+2 k pf: Sk : denote the min possible value of size(z) over all nodes z such that z.degree=k. Trivially, S0=1, S1=2, and S2=3 Sk size(x) , size(y1) 1 size(x) Sk 2+ i=2, ,k Si-2 By induction on k that Sk Fk+2 Clearly for k=0 and 1 Assume that k 2 and that Si Fi+2for i=0, ,k-1 We have Sk 2+ i=2, ,k Si-2 2+ i=2, ,k Fi = 1+ i=0, ,k Fi = Fk+2 Thus, size(x) Sk Fk+2 k x yk y1 y2 Sk-2 S0 p30.

31. Corollary 4: The max degree D(n) of any node in an n-node Fibonacci heap is O(lg n) pf: x: any node in an n-node Fibonacci heap k=degree[x] n size(x) k log n k Thus the max degree D(n) of any node is O(lg n) p31.