algorithmdata-structuresheapfibonaccifibonacci-heap

Need help understanding how to decrease key in Fibonacci heap

I'm trying to understand how to implement Fibonacci heap operations. Given we have the following heap:

enter image description here

How would we decrease 35 to 27, for example? The order is not preserved since 27 is not greater than 30, so we must rebuild the heap. So where does 27 go? Under 5?

Solution

  • In a Fibonacci heap, decrease-key actually cuts out any nodes from a tree whose key decreases below the parent's key. In your case, the node would be put up into the root list as a singleton node.

    More generally, decrease-key works as follows:

    1. Decrease the key.
    2. If the node's new key is greater than its parent's, stop.
    3. If the node is a root, stop.
    4. Unmark the node and cut it from its parent.
    5. If the parent was unmarked, mark it.
    6. If the parent was marked, go to (3).

    Hope this helps!