Chapter: Programming and Data structures : Advanced Non-Linear Data Structures

Fibonacci Heaps

A binomial tree of order 0 is a single node. A binomial tree of order k has a root of degree k and its children are roots of binomial trees of orders k-1, k-2, ..., 2, 1, 0 (in order).

FIBONACCI HEAPS:

Binomial Tree:

 

A binomial tree of order 0 is a single node. A binomial tree of order k has a root of degree k and its children are roots of binomial trees of orders k-1, k-2, ..., 2, 1, 0 (in order). A binomial tree of order k has 2k nodes.


Data Structures:

 

·        Heap ordered Trees

 

·   Rooted, but unordered

 

·        Children of a node are linked together in a Circular, doubly linked List, E.g node 52

 

Node Pointers

 

-  left [x]

 

-  right [x]

 

-  degree [x]

 

-  number of children in the child list of x

 

-  mark [x]

 

 

Properties:

 

·        Collection of unordered Binomial Trees.

 

·        Support Mergeable heap operations such as Insert, Minimum, Extract Min, and Union in constant time O(1)

 

·        Desirable when the number of Extract Min and Delete operations is small relative to the number of other operations.

 

·        Most asymptotically fastest algorithms for computing minimum spanning trees and finding single source shortest paths make use of the Fibonacci heaps.

 

 

Fibonacci Heap Operations:

 

Make Fibonacci Heap

 

·        Assign N[H] = 0, min[H] = nil

 

·        Amortized cost is O(1)

 

Find Min

 

·        Access Min[H] in O(1) time

 

Uniting 2 Fibonacci Heaps

 

·        Concatenate the root lists of Heap1 and Heap2

 

·        Set the minimum node of the new Heap

 

·        Free the 2 heap objects

 

·        Amortized cost is equal to actual cost of O(1)

 

Insert

 

·        Amortized cost is O(1)

 

·        Initialize the structural fields of node x, add it to the root list of H

 

·        Update the pointer to the minimum node of H, min[H]

 

·        Increment the total number of nodes in the Heap, n[H]

 

Example:


 

·   Node 21 has been inserted

 

·        Red Nodes are marked nodes – they will become relevant only in the delete operation.

 



Extract Minimum Node

 

·        Amortized cost is O(D(n))

 

·        Make a root out of each of the minimum node‟s children.

 

·        Remove the minimum node from the root list, min ptr to right(x)

 

·        Consolidate the root list by linking roots of equal degree and key[x] <= key[y], until every root in the root list has a distinct degree value. (uses auxiliary array)


 

·        Root Nodes are stored in the auxiliary array in the index corresponding to their degree.

 

·        Hence node 7 is stored in index 3 and node 21 is stored in index 0.

 

·        Further, node 18 is stored in index 1

 

·        There are no root nodes of index 2, so that array entry remains empty

 

·        Now the algorithm iterates through the auxiliary array and links roots of equal degree such that key[x] <= key[y],


 

·        Nodes 21 and 52 are linked so that node 21 has degree 1, and it is then linked to node 18


·        The pointers of the auxiliary array are updated.

 

·        But there are now no more remaining root nodes of duplicate degrees.


·   Extract-Min is now done.

 

·        The pointer min[H] is finally updated to the new minimum.


A node is marked if:

 

·        At some point it was a root then it was linked to anther node and 1 child of it has been cut.

 

·        Newly created nodes are always unmarked

 

·        A node becomes unmarked whenever it becomes the child of another node.

 

Decrease-Key

 

·        Amortized cost is O(1).

 

·        Check that new key is not greater than current key, then assign new key to x

 

·        If x is a root or if heap property is maintained, no structural changes

 

·        Else

 

o  Cut x: make x a root, remove link from parent y, clear marked field of x

 

o   Perform a Cascading cut on x‟s parent y (relevant if parent is marked):

§    if unmarked: mark y, return

 

§    if marked: Cut y, recurse on node y‟s parent

 

§    if y is a root, return

 

·        The Cascading cut procedure recurses its way up the tree until a root, or an unmarked node is found.

 

·        Update min[H] if necessary.

 

Example:

 

·        Suppose we want to decrease the keys of node 46  to 15.


 

·        Since the new key of node 46 is 15 it violates the min-heap property, so it is cut and put on the root.

 

·        Suppose now we want to decrease the key of node 35 to 5.


·        So node 5 is cut and place on the root list because again the heap property is violated.

 

·        But the parent of node 35, which is node 26, is marked, so we have to perform a

 

cascading cut.


·        The cascading cut involves cutting the marked node, 26, unmarking it, and putting it on the root list.

·        We now repeat this procedure (recurse) on the marked nodes parent until we hit a node on the root list.


·        Since the next node encountered in the cascading cut procedure is a root node – node 7 – the procedure terminates.

·        Now the min heap pointer is updated.



Delete-Key

 

·        Amortized cost is O(D(n))

 

·        Call Decease-Key on the node x that needs to be deleted in H, assigning negative infinity to it.

 

·        Call Extract-Min on H.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Fibonacci Heaps |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.