Fibonacci Heap Operations

Create and Peek-Min

Create returns (NIL, 0), an empty heap pointer and zero count. Peek-min returns the key and payload of the node pointed to by min_ptr, or NIL if the heap is empty. Both are $\Theta(1)$.

Insert

To insert (key, payload) into heap fh:

1. Create a new singleton node (left and right point to itself, parent and child NIL, marked false, degree 0).
2. Call destructive-union(fh, new_node).

Since union splices the new node into the root list and updates min_ptr if needed, insert is $\Theta(1)$ actual and amortised.

Destructive Union (Merge)

Given two heap handles (p1, n1) and (p2, n2):

1. If either p is NIL, return the other.
2. Splice the two root lists together (using DLL-SPLICE on the circular doubly linked lists).
3. Set the new min_ptr to whichever of p1, p2 has the smaller key.
4. Return (winning_ptr, n1 + n2).

All steps are constant time. The splice operation is:

• a.left = c, c.right = a
• b.right = d, d.left = b

The amortised cost is $\Theta(1)$ because the potential function (trees + 2×marked) adds the two separate potentials; no new trees or marks are created.

Extract-Min

This is the most expensive operation, where all deferred work is done.

Step 1 — Promote children: The minimum node is identified via min_ptr. All its children are moved to the root list. For each child, parent is set to NIL and marked to false.

Step 2 — Remove old minimum: Splice the old minimum out of the root list. Decrement n.

Step 3 — Consolidate: Create an array A[0..D(n)] initialised to NIL, where $D(n) \le \lfloor \log_\phi n \rfloor$ is the maximum possible degree (with $\phi = (1+\sqrt{5})/2$, the golden ratio).

Walk around the root list. For each node t:

• If A[t.degree] is NIL, set A[t.degree] = t.
• Else, merge t with A[t.degree]: the node with the larger key becomes the child of the node with the smaller key. The larger node is removed from the root list. The winner’s degree increments by 1. If A[new_degree] is occupied, recursively merge. This is similar to binary addition of binomial trees.

After consolidation, at most one tree of each degree remains, so the root list has at most $D(n)+1$ trees.

Step 4 — New minimum: During the walk, track the node with the smallest key; update min_ptr.

Actual cost can be $\Theta(n)$ (many children to process), but amortised cost is $\Theta(\log n)$ because consolidation reduces the root list from potentially many trees down to $O(\log n)$.

Decrease-Key

Given a pointer ptr_k to a node and a new key nk (must be $\le$ current key):

1. Set ptr_k.key = nk.
2. If ptr_k is in the root list, or its new key is $\ge$ its parent’s key, update min_ptr if needed and stop.
3. Otherwise: cut ptr_k from its parent (via helper CHOP-OUT), splice it into the root list, and mark its parent.
4. If the parent was already marked, then cascading cut: chop out the parent as well, unmark it, splice it into the root list, and recurse on its parent.

CHOP-OUT handles updating the parent’s child pointer, decrementing the parent’s degree, and setting the cut node’s marked = false (since root list nodes are never marked). Amortised cost is $\Theta(1)$; actual cost is $O(h)$ where $h$ is the height of cascading cuts, which the potential function covers.

Delete

delete(fh, ptr_k) is implemented as decrease-key(fh, ptr_k, -∞) followed by extract-min(fh). Amortised cost $\Theta(\log n)$.

Worked Example: Extract-Min with Consolidation

Starting state: root list has trees of degrees 0, 0, 1, 0, 2, 1. Array size $D(6)+1 = 4$.

Step	Root	A[0]	A[1]	A[2]	A[3]	Action
1	t(deg 0)	t0	—	—	—	Store at index 0
2	t(deg 0)	—	—	—	—	Merge with A[0] → deg 1
3	merged(deg 1)	—	t1	—	—	Store at index 1
4	t(deg 1)	—	—	—	—	Merge with A[1] → deg 2
5	merged(deg 2)	—	—	t2	—	Store at index 2
6	t(deg 0)	t3	—	t2	—	Store at index 0
7	t(deg 2)	t3	—	—	—	Merge with A[2] → deg 3
8	merged(deg 3)	t3	—	—	t3	Store at index 3

Final root list: at most 4 trees (degrees 0, 0, 0, 3).

Summary

Operation	Actual Cost	Amortised Cost
Create	$\Theta(1)$	$\Theta(1)$
Peek-min	$\Theta(1)$	$\Theta(1)$
Insert	$\Theta(1)$	$\Theta(1)$
Destructive-union	$\Theta(1)$	$\Theta(1)$
Extract-min	$\Theta(n)$ worst	$\Theta(\log n)$
Decrease-key	$O(h)$ worst	$\Theta(1)$
Delete	—	$\Theta(\log n)$
Count	$\Theta(1)$	$\Theta(1)$