Marking and Cascading Cuts

The Mark Bit

Each node in a Fibonacci heap carries a boolean marked flag. By definition:

A node is marked if it has lost exactly one child since it became a child of its current parent.

Nodes in the root list are never marked (they have no parent, so the concept is meaningless for them). When a node is first cut and moved to the root list, its marked flag is reset to false.

When Does Marking Occur?

When decrease-key causes a node x to violate the min-heap property (new key < parent’s key):

1. x is cut from its parent and moved to the root list.
2. If x’s parent p is not in the root list, we mark p.
3. If p was already marked, we cut p as well — this is the cascading cut.

The rule: a node can lose at most one child and remain in place. Losing a second child forces the node itself to be cut.

Cascading Cut Algorithm

decrease-key(fh, ptr_k, nk):
    ptr_k.key = nk
    if ptr_k.parent != NIL and ptr_k.key < ptr_k.parent.key:
        do:
            if !ptr_k.parent.marked:
                CHOP-OUT(fh, ptr_k)
                break
            else:
                CHOP-OUT(fh, ptr_k)
                ptr_k = ptr_k.parent
        while ptr_k.parent != NIL
    if fh.min_ptr.key > nk:
        fh.min_ptr = ptr_k_orig

CHOP-OUT performs:

• Update parent’s child pointer (if this was the only/designated child)
• Decrement parent’s degree
• If parent has a parent (i.e. is not a root), mark it
• Remove the node from its sibling list
• Set node’s parent = NIL, marked = false, left = right = itself
• Splice into root list

The loop propagates upward: as long as the parent was already marked, it gets cut too, and we continue to its parent.

Why Cascading Cuts? The Grandchild Rule

The cascading cut rule guarantees a crucial structural invariant, sometimes called the grandchild rule:

Consider a node $x$ with degree $d$. Order its children $y_1, y_2, \ldots, y_d$ by the time they became children of $x$ (earliest first). Then for all $i \in \{1, \ldots, d\}$, the number of grandchildren of $x$ via child $y_i$ satisfies: $\text{children}(y_i) \ge i - 2$

Reasoning: When $x$ acquired child $y_i$, both $x$ and $y_i$ had degree $i-1$ (since $x$ already had $i-1$ children). After the link, $y_i$ could lose at most one child (the second loss would trigger a cascading cut, separating $y_i$ from $x$). So $y_i$‘s degree is at least $(i-1) - 1 = i-2$.

This gives the name “Fibonacci heap” because this recurrence leads to Fibonacci numbers.

The Fibonacci Number Connection

Let $s_d$ be the minimum number of nodes in a subtree whose root has degree $d$. From the grandchild rule:

$s_d \ge 2 + \sum_{i=2}^{d} s_{i-2}$

With base cases $s_0 = 1$, $s_1 = 2$. By induction, $s_d \ge F_{d+2}$ where $F_k$ is the $k$-th Fibonacci number ($F_1 = 1, F_2 = 1, F_3 = 2, \ldots$). Since $F_{d+2} \ge \phi^d$ with $\phi = (1+\sqrt{5})/2 \approx 1.618$, we get $d \le \log_\phi n = O(\log n)$.

Worked Example: Cascading Cut Chain

Consider a min-heap tree: root $R$ (key 3, marked false) has children $A$ (key 5, marked false), $B$ (key 8, marked false). $A$ has child $C$ (key 10, marked false). $C$ has child $D$ (key 12).

       3(R)
      /    \
    5(A)   8(B)
    /
  10(C)
  /
12(D)

Step 1: Call decrease-key on D, setting key to 1. Since $1 < 10$ (C’s key), cut D. D goes to root list. C becomes marked. C was unmarked, so stop.

Roots: [D:1]  +  3(R)-5(A)-10(C✓)-8(B)

Step 2: Call decrease-key on C, setting key to 2. Since $2 < 5$ (A’s key), cut C. C goes to root list, unmarked. A was unmarked, becomes marked. Stop.

Roots: [D:1, C:2]  +  3(R)-5(A✓)-8(B)

Step 3: Call decrease-key on A, setting key to 0. Since $0 < 3$ (R’s key), cut A. A goes to root list, unmarked. R is a root (parent NIL), so R is not marked. Stop.

Roots: [D:1, C:2, A:0]  +  3(R)-8(B)

Step 4: Alternative scenario where cascading triggers. Suppose after step 1, we call decrease-key on C (key 3) while A was already marked. Cut C. C goes to root list. A is already marked, so A is also cut! A goes to root list. Now check A’s parent R. R was not marked, so mark R and stop. Two nodes cut for the price of one decrease-key.

Summary

Concept	Rule
Mark bit	Set when a node loses its first child
Cascading cut	Triggered when a marked node loses a second child
Root nodes	Never marked
Cut node	Becomes unmarked on entering root list
Grandchild rule	$y_i$’s degree $\ge i-2$ when ordered by attachment time
Structural guarantee	$s_d \ge F_{d+2}$, implying $d = O(\log n)$
Name origin	Minimum subtree sizes grow like Fibonacci numbers