Operations On Fibonacci Heaps

The strength of Fibonacci heaps lies in their use of circular doubly linked lists and lazy restructuring, which enables constant-time operations and amortized complexities.

As with binary heaps, Fibonacci heaps do not support efficient search. Therefore, operations like decrease-key and delete assume direct access to the node, not just its key.

In practice, an auxiliary structure (e.g. a dictionary) is often used to map keys to nodes, allowing amortised constant-time lookup at the cost of linear additional space.

Merge Operation

The merge operation combines two Fibonacci heaps, $H_1$ and $H_2$, by joining their root lists, i.e. concatenating two circular doubly linked lists:

1. Bi-directionally, connect the rightmost sibling of $H_1$ to the leftmost sibling of $H_2$
2. Bi-directionally, connect the leftmost sibling of $H_1$ to the rightmost sibling of $H_2$.
3. Set H.min as the min(H₁.min, H₂.min)

Since root lists are circular and accessible via their minimum nodes, merging takes $O(1)$ time.

Example Of Merging

MULTI COLUMN

Node 7 (rightmost in $H_1$) is connected to node 33 (leftmost in $H_2$), and node 4 (rightmost in $H_2$) connects back to the leftmost of $H_1$. H.min is updated to the smaller of the two minimums.

Insertion Operation

The insert operation adds a new node to a Fibonacci heap $H$ in $O(1)$ time as follows:

1. Access the heap via the H.min pointer
2. Insert the new node into the root_list, typically as the left sibling of H.min
3. If the new node’s key is smaller than H.min, update H.min to point to the new node.

Insertion is done to the left for consistency, though the position is arbitrary due to the unordered nature of the root list.

Example Of Insert

Extract-Min Operation

The extract-min operation removes the node with the minimum key from the Fibonacci heap:

1. Identify the minimum node via the H.min pointer.
2. Remove this node from the root list via delete operation.
3. Promote all its children to the root list in $O(1)$ via pointer manipulation
   • The children, stored in a circular doubly linked list, are spliced directly into the root list.
   • This involves reconnecting:
     • The leftmost child to the node left of the removed node, and
     • The rightmost child to the node right of the removed node.
   • Each promoted child’s parent pointer is set to null.
4. Set H.min to temporarily to the right sibling of H.min
5. Run the consolidate operation to merge trees of the same degree

Before consolidation, the root list may contain multiple trees of the same degree. Afterward, the heap maintains at most one tree per degree, restoring the Fibonacci heap properties.

Example Of Extract Min

Consolidation Operation

The consolidate operation merges trees of the same degree to ensure the heap contains at most one tree of any given degree, maintaining the Fibonacci heap properties. It only executes after an extract-min operation.

1. Initialise an auxiliary array A of size $\lfloor {\log }_{2}n\rfloor +1$ with null, where A[d] stores a pointer to a tree root of degree d.
2. Initialise current = H.min for node traversal and final = current.left to check when a full cycle is complete.
3. Traverse each node in the root list, ensuring there is at most one tree of any degree
   • Let x = current and d = current.degree
   • If x is the first tree encountered with degree d (i.e. A[d] = null) then:
     • Set A[d] = x
     • Point current to the next distinct node in the root list.
     • If current = final, a full cycle is complete, and at most one tree of any degree exists.
   • Else if another node y has already been encountered with degree d (A[d] != null) then:
     • Merge (consolidate) the two trees together, maintaining the heap-property.
     • Set A[d] = null
     • Point current to the root of the merged tree.
4. Additionally, during traversal, keep track of the minimum root encountered, and update H.min.

The amortised time complexity of consolidate and extract-min is $O(\log N)$. This, along with the space complexity of A, is due to the fact that the maximum degree of any node in a Fibonacci heap is $O(\log N)$ — see proof

Example Of Consolidate

Using the above example of extract-min, initialise an auxiliary array of size $\lfloor ({\log }_2(14))\rfloor +1=4$ and initialise current = 17 and final = current.left = 38

The root node at current = 17 has degree $1$, and A[1] is empty, thus set A[1] = current = 17, and point current to the right sibling 24

The same applies for current = 24 and current = 23. After those nodes, current = 7

The root node at current = 7 has degree $0$, but A[0] = 23 so merge (consolidate) these trees whilst maintaining min-heap property. As 7 < 23, node 23 becomes the child of node 7.

Lastly set A[0] to empty, and point current to the root of the merged tree i.e. current = 7

The same applies for the next two iterations as current = 7 has degree $1$ (A[1] = 17), and then when merged would have degree $2$ (A[2] = 24), resulting in a merged tree of degree $3$ (A[3] = null).

Continue this process until all nodes have been checked, i.e. current = final

Decrease-Key Operation

The decrease-key operation in a Fibonacci heap reduces the key of a given node to a new, smaller value:

Case 1: When decrease-key(x -> y) does not violate the heap property i.e. parent < y

1. Simply decrease the key on this node. No restructuring is required.

Case 2: When decrease-key(x -> y) does violate the heap property i.e. parent > y

1. Promote the subtree rooted at y (previously x) to the root_list
2. Update H.min if necessary
3. If y was marked before, unmark it after promoting.
4. If the parent was originally unmarked (i.e. hasn’t yet lost a child) mark it to indicate that it has lost a child.
5. Else if the parent was marked, repeat this promotion process with the parent node.

The amortised complexity of decrease-key is $O(1)$

Note that if the parent at the root lost a child, there is no need to mark it

However, due to extract-min/consolidate, there could appear a node in the root list that is marked.

It is important that during extract-min/consolidate, the mark is never altered as it impacts the amortised analysis.

Example of Decrease-Key (Case 1)

For the resultant tree of the consolidate example, if node 17 were to be reduced to 9 (i.e. decrease-key(17, 9)), the parent of this node 7 is still less than 9, so the min-heap property is maintained and no restructuring is required.

Example Of Decrease-Key (Case 2)

For the resultant tree of the consolidate example:

2A — If 46 were to be reduced to 15, then the min-heap property is violated as its parent 24 > 15. To address this violation:

• Promote the subtree rooted at 15 to the root_list, no need to update H.min
• Since parent 24 was originally unmarked (i.e., hasn’t yet lost a child), mark it.

2B — If 35 were to be reduced to 5, then the min-heap property is violated as its parent 26 > 5. Additionally, the parent has already been marked, to address this:

• Promote the subtree rooted at 5 to the root_list and update H.min since 5 > 7
• Since parent 26 was originally marked (i.e., has lost a child), then repeat this process with 26.

• Promote the subtree rooted at 26 to the root_list and unmark it.
• Since the parent 24 was originally marked repeat this process with it.

• Promote the subtree rooted at 24 to the root_list and unmark it
• Since its parent 7 was originally unmarked, we would normally mark it, but as its in the root, we can let it be.

Delete Operation

The delete operation deletes some specified node from the Fibonacci Heap. It can be done simply by:

1. decrease-key the node to $-\infty$
2. extract-min

This removes the node in amortised $O(\log N)$ time