Fibonacci Heaps – DEV Community

This post explores one of computer science’s most beautiful data structures—the Fibonacci Heap.

The Fibonacci Heap is a specialized priority queue data structure consisting of a collection of heap-ordered trees. Each tree satisfies the min-heap property.

The Fibonacci Heap is a specialized priority queue data structure consisting of a collection of heap-ordered trees. Each tree satisfies the min-heap property, meaning each parent node has a key less than or equal to its children’s keys. Let’s explore this clever data structure’s technical details and inner workings.

A Fibonacci heap consists of multiple trees stored in a circular doubly-linked list called the root list. Each node within these trees contains pointers to:

• Its parent node
• One of its children
• Its left and right siblings (due to the circular doubly-linked nature)
• A boolean “marked” flag indicating whether it has lost a child since becoming a child of another node.

This linked structure allows constant-time insertion, deletion, and merging operations by updating pointers.

Key Operations:

Insert Operation

The idea is to be lazy; here, we add the number to the root list and then update the pointer to the minimum element.
This operation is performed in O(1) amortized time complexity.

Merge Operation

While merging two Fibonacci, we join both root lists by updating the root node to whichever has the smallest key. And the other root node points to it.

Extract-Min Operation

Extracting the minimum element is more complex and has multiple steps:

1. Remove Minimum Node:

   • Remove the node pointed to by the minimum pointer from the root list.
   • Add all its children directly into the root list as separate trees.

2. Clean Up:

   We must reduce the number of trees in our root list to maintain efficiency. We do this by repeatedly merging trees with identical degrees:

   • We use an auxiliary array indexed by node degree.
   • We only allow one node to exist per degree and merge if there is more than one.

This ensures that no two trees have identical degrees after Extract-Min completes, keeping node degrees low.

1. Update Minimum Pointer:
   All resulting trees have distinct degrees, just like a Binomial Heap.

Decrease-Key Operation

Decrease-Key operation reduces a node’s key value and adjusts its position within the heap:

• Decrease the key value directly at its current position.
• If this violates the heap property (the node becomes smaller than its parent), remove that node from its parent and move it to the root list.
• Mark any parent losing one child; if a marked parent loses another child later, cut that parent out recursively as well.
• Update minimum pointer if necessary.

The above technique is known as controlled Node Cuts or Cascading Cuts. It ensures that each node retains a certain minimum number of descendants relative to its degree.

• Specifically, for any given node with degree d, the smallest possible subtree rooted at that node contains at least F_{d+2} nodes, where F_i denotes the i th Fibonacci number.

Why Fibonacci Numbers Appear:

Now consider the smallest possible tree for each degree after allowing cascading cuts:

• A tree with degree 0 has 1 node.
• A tree with degree 1 also minimally has 2 nodes.
• Each subtree rooted at a child node must have at least certain minimal degrees for higher degrees due to our “one-child-loss” rule.
• It turns out that this minimal subtree size precisely follows the Fibonacci sequence:
  • The size of the smallest possible tree for degree d equals the sum of sizes of two previous smaller-degree minimal trees, which exactly matches how Fibonacci numbers are defined.

For example:

• A degree-0 tree contains F_2 = 1 node.
• A degree-1 tree contains F_3 = 2 nodes.
• A degree-2 tree contains F_4 = 3 nodes.
• A degree-3 tree contains F_5 = 5 nodes.
• A degree-4 tree contains F_6 = 8 nodes.

In conclusion, Fibonacci Heaps balances laziness (fast Insert and DecreaseKey) with periodic cleanup (ExtractMin consolidations), ensuring optimal amortized complexity for priority queue operations. This design leverages amortization and binomial tree structures to achieve these impressive theoretical guarantees.

This insightful YouTube video explains The Fibonacci Heap operations in detail: https://www.youtube.com/watch?v=6JxvKfSV9Ns&t=1561s