Fibonacci Heap – Deletion, Extract min and Decrease key

Fibonacci Heap – Deletion, Extract min and Decrease key

In the last post, we discussed Insertion and Union of Fibonacci Heaps. In this post, we will discuss Extract_min(), Decrease_key() and Deletion() operations on Fibonacci heap.
Extract_min(): We create a function for deleting the minimum node and setting the min pointer to the minimum value in the remaining heap. The following algorithm is followed:


  1. Delete the min node.
  2. Set head to the next min node and add all the tree of the deleted node in root list.
  3. Create an array of degree pointers of the size of the deleted node.
  4. Set degree pointer to current node.
  5. Move to the next node.
    • If degrees are different then set degree pointer to next node.
    • If degrees are same then join the Fibonacci trees by union operation.
  6. Repeat steps 4 and 5 until the heap is completed.
Example:
Decrease_key(): To decrease the value of any element in the heap, we follow the following algorithm:
  • Decrease the value of the node ‘x’ to the new chosen value.
  • CASE 1) If min heap property is not violated,
    • Update min pointer if necessary.
  • CASE 2) If min heap property is violated and parent of ‘x’ is unmarked,
    • Cut off the link between ‘x’ and its parent.
    • Mark the parent of ‘x’.
    • Add tree rooted at ‘x’ to the root list and update min pointer if necessary.
  • CASE 3)If min heap property is violated and parent of ‘x’ is marked,
    • Cut off the link between ‘x’ and its parent p[x].
    • Add ‘x’ to the root list, updating min pointer if necessary.
    • Cut off link between p[x] and p[p[x]].
    • Add p[x] to the root list, updating min pointer if necessary.
    • If p[p[x]] is unmarked, mark it.
    • Else, cut off p[p[x]] and repeat steps 4.2 to 4.5, taking p[p[x]] as ‘x’.
    • Example:
    Deletion(): To delete any element in a Fibonacci heap, the following algorithm is followed:
    1. Decrease the value of the node to be deleted ‘x’ to minimum by Decrease_key() function.
    2. By using min heap property, heapify the heap containing ‘x’, bringing ‘x’ to the root list.
    3. Apply Extract_min() algorithm to the Fibonacci heap.
    Example:

    Comments

    Post a Comment

    Popular posts from this blog

    Fibonacci Heap

    Image
    Fibonacci Heap . 1) Find Min: Θ(1) [Same as both Binary and Binomial] 2) Delete Min: O(Log n) [Θ(Log n) in both Binary and Binomial] 3) Insert: Θ(1) [Θ(Log n) in Binary and Θ(1) in Binomial] 4) Decrease-Key: Θ(1) [Θ(Log n) in both Binary and Binomial] 5) Merge: Θ(1) [Θ(m Log n) or Θ(m+n) in Binary and Θ(Log n) in Binomial] Like  Binomial Heap , Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be Binomial Tree). Below is an example Fibonacci Heap taken from  here . Fibonacci Heap maintains a pointer to minimum value (which is root of a tree). All tree roots are connected using circular doubly linked list, so all of them can be accessed using single ‘min’ pointer. The main idea is to execute operations in “lazy” way. For example merge operati
    Read more

    Tracable and Non Tracable problems

    Tractable and Intractable Problems So far, almost all of the problems that we have studied have had complexities that are polynomial, i.e. whose running time T(n) has been O(n^k) for some fixed value of k. Typically k has been small, 3 or less. We will let P denote the class of all problems whose solution can be computed in polynomial time, i.e. O(n^k) or some fixed k, whether it is 3, 100, or something else. We consider all such problems efficiently solvable, or tractable. Notice that this is a very relaxed definition of tractability, but our goal in this lecture and the next few ones is to understand which problems are intractable, a notion that we formalize as not being solvable in polynomial time. Notice how not being in P is certainly a strong way of being intractable. We will focus on a class of problems, called the NP-complete problems, which is a class of very diverse problems, that share the following properties: we only know how to solve those problems in time much larger
    Read more

    Amortized analysis- Splay Tree

    A splay tree is an efficient implementation of binary search trees that takes advantage of locality in the incoming lookup requests. Locality in this context is a tendency to look for the same element multiple times. A stream of requests exhibits no locality if every element is equally likely to be accessed at each point. For many applications, there is locality, and elements tend to be accessed repeatedly. A good example of an application with this property is a network router. Routers must decide on which outgoing wire to route the incoming packets, based on the IP address in the packets. The router needs a big table (a map) that can be used to look up an IP address and find out which outgoing connection to use. If an IP address has been used once, it is likely to be used again, perhaps many times. Splay trees are designed to provide good performance in this situation. In addition, splay trees offer amortized O(lg n) performance. That is, a sequence of M operations on an n-node s
    Read more