Strict Fibonacci heap

Strict Fibonacci heap
Type	Heap
Invented	2012
Invented by	Gerth S. Brodal, George Lagogiannis, and Robert E. Tarjan
Complexities in big O notation
Space complexity Time complexity Function Amortized Worst case Insert Θ(1) Find-min Θ(1) Delete-min O(log n) Decrease-key Θ(1) Merge Θ(1)

In computer science, a strict Fibonacci heap is a priority queue data structure with worst case time bounds equal to the amortized bounds of the Fibonacci heap. Along with Brodal queues, strict Fibonacci heaps belong to a class of asymptotically optimal data structures for priority queues. All operations on strict Fibonacci heaps run in worst case constant time except delete-min, which is necessarily logarithmic. This is optimal, because any priority queue can be used to sort a list of $n$ elements by performing $n$ insertions and $n$ delete-min operations. Strict Fibonacci heaps were invented in 2012 by Gerth Stølting Brodal, George Lagogiannis, and Robert E. Tarjan.

Structure

A strict Fibonacci heap. Nodes 5 and 2 are active roots.

A strict Fibonacci heap is a single tree satisfying the minimum-heap property.

The nodes in the heap have the following rules:

• All nodes are either active (colored white) or passive (colored red).
• The root is passive.
• For any node, the active children lie to the left of the passive children.

We also make the following definitions:

• An active root is an active node with a passive parent.
• A passive linkable node is a passive node where all its descendants are passive (a passive node with no children is considered to be linkable).
• The rank of an active node is the number of active children it has.
• The loss of an active node is the number of active children it has lost.
• An active root always has loss 0 (similar to how ordinary Fibonacci tree roots are always unmarked).

To facilitate root degree reduction (described below), the passive linkable children of the root always lie to the right of the passive non-linkable children.

Every non-root node also participates in a queue $Q$, which assists in keeping the degrees of nodes logarithmic during the delete-min operation.

Invariants

In the rest of this article, let the real number $R$ be defined as $2\lg n+6$, where $n$ is the number of nodes in the heap, and $\lg$ denotes the binary logarithm. The structure of strict Fibonacci heaps is governed by five invariants, which impose logarithmic bounds on quantities.

Invariant 1

The $i$th rightmost active child $c_{i}$ of an active node satisfies $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1$.

Invariant 2

The total number of active roots is at most $R+1$.

Invariant 3

The total loss in the heap is at most $R+1$.

Invariant 4

The degree of the root is at most $R+3$.

Invariant 5

For an active node with loss 0, the maximum degree is bounded by $2\lg(2n-p)+10$, where $p$ is its position in $Q$ (with 1 as the first element). For all other non-root nodes, the degree is bounded by $2\lg(2n-p)+9$.

We also derive some fundamental facts about strict Fibonacci heaps, which allow us to apply the pigeonhole principle and show that the priority queue operations preserve the invariants.

Corollary 1—The degree of any non-root node is at most $R+6$.

Proof

This follows immediately from invariant 5. Letting $p=0$, we have $2\lg(2n-0)+10=2\lg n+12=R+6$

Lemma—If invariant 1 holds, then the maximum rank $r$ or any active node is at most $\lg n+{\sqrt {2L}}+2$, where $L$ is the total loss.

Proof

We proceed by contradiction. Let $x$ be an active node with maximal rank $r$ in a heap with $n$ nodes and total loss $L$, and assume that $r\geq \lg n+k+1$, where $k$ is the smallest integer such that $k(k+1)/2\geq L$. Our goal is to show that the subtree $T_{x}$ rooted at $x$ contains $n+1$ nodes, which is a contradiction because there are only $n$ nodes in the heap.

Discard all passive nodes and their descendants from $T_{x}$, leaving it with only active nodes. Cut off all the grandchildren of $x$ whose subtrees contain any node of positive loss, and increase the loss of the children of $x$ accordingly, once for each grandchild lost. The total loss is still at most $L$. The children of $x$ now consists of loss-free subtrees and leaf nodes with positive loss, and still satisfy invariant 1, that is, $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1$ for the $i$th rightmost child of $x$. We reduce $T_{x}$ to an incomplete binomial tree by making $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} =i-1$ exactly. For each direct child $c_{i}$ of $x$, reduce its loss first, and prune any grandchildren until $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} =i-1$. All other descendants of $x$ are converted into binomial subtrees by pruning children as necessary.

We now attempt to reconstruct a minimal version of $T_{x}$ by starting with a binomial tree of degree $r$, containing $2^{r}$ active nodes. We wish to increase the loss to $L$, but keep the rank of $x$ as $r$ and the number of nodes as low as possible. For a binomial tree of degree $r$, there is one child of each degree from $0$ to $r-1$. Hence, there are $j$ grandchildren of order $r-j-1$. If we cut all the grandchildren whose degree $\leq r-k-1$, then we have cut ${\textstyle \sum _{j=1}^{k}j=k(k+1)/2}$ grandchildren, which is sufficient to bring the loss up to $L$. All grandchildren with degree $\leq r-k-2$ survive. Let $w$ be the child of $x$ with degree $r-k-1$ and loss 0. By assumption, $r-k-1\geq \lg n$, and $w$ is a complete binomial tree, so it has at least $2^{\lg n}=n$ nodes. Since this would mean $T_{x}$ has at least $n+1$ nodes, we have reached a contradiction, and therefore $r<\lg n+k+1$. Noting that $k<{\sqrt {k(k+1)}}={\sqrt {2L}}$, we obtain $r<\lg n+{\sqrt {2L}}+2$.

Corollary 2—If invariants 1 and 3 both hold, then the maximum rank is $R$.

Proof

We have that $L\leq R+1$ from invariant 3. By substituting into lemma 1, we calculate as follows:

${\begin{aligned}r&\leq \lg n+{\sqrt {2L}}+2\\&\leq \lg n+{\sqrt {2(R+1)}}+2\\&=\lg n+{\sqrt {4\lg n+14}}+2\\&\leq \lg n+{\sqrt {(\lg n)^{2}+2\cdot 4\lg n+4^{2}}}+2\\&=\lg n+(\lg n+4)+2\\&=R\end{aligned}}$

Transformations

The following four transformations are intended to restore the above invariants after a priority queue operation has been performed. There are three main quantities we wish to minimize: the degree of the root, the total loss in the heap, and the number of active roots. All transformations can be performed in $O(1)$ time, which is possible by maintaining auxilliary data structures to track candidate nodes (described in the section on implementation).

Active root reduction

Let $x$ and $y$ be active roots with equal rank $r$, and assume $x.\mathrm {key} \leq y.\mathrm {key}$. Link $y$ as the leftmost child of $x$ and increase the rank of $x$ by 1. If the rightmost child $z$ of $x$ is passive, link $z$ to the root.

As a result, $y$ is no longer an active root, so the number of active roots decreases by 1. However, the degree of the root node may increase by 1,

Note that, since $y$ becomes the $(r+1)$th rightmost child of $x$, and $y$ has rank $r$, invariant 1 is preserved.

Root degree reduction

Let $x$, $y$, and $z$ be the three rightmost passive linkable children of the root. Detach them all from the root and sort them such that $x.\mathrm {key} \leq y.\mathrm {key} \leq z.\mathrm {key}$. Change $x$ and $y$ to be active. Link $z$ to $y$, $y$ to $x$, and $x$ to the root. As a result, $x$ becomes an active root with rank 1 and loss 0. The rank and loss of $y$ is set to 0.

The net change of this transformation is that the degree of the root node decreases by 2. As a side effect, the number of active roots increases by 1.

One node loss reduction

Let $x$ be an active non-root with loss at least 2. Link $x$ to the root, thus turning it into an active root, and resetting its loss to 0. Let the original parent of $x$ be $y$. $y$ must be active, since otherwise $x$ would have previously been an active root, and thus could not have had positive loss. The rank of $y$ is decreased by 1. If $y$ is not an active root, increase its loss by 1.

Overall, the total loss decreases by 1 or 2. As a side effect, the root degree and number of active roots increase by 1, making it less preferrable to two node loss reduction, but still a necessary operation.

Two node loss reduction

Let $x$ and $y$ be active nodes with equal rank $r$ and loss equal to 1, and let $z$ be the parent of $y$. Without loss of generality, assume that $x.\mathrm {key} \leq y.\mathrm {key}$. Detach $y$ from $z$, and link $y$ to $x$. Increase the rank of $x$ by 1 and reset the loss of $x$ and $y$ from 1 to 0.

$z$ must be active, since $y$ had positive loss and could not have been an active root. Hence, the rank of $z$ is decreased by 1. If $z$ is not an active root, increase its loss by 1.

Overall, the total loss decreases by 1 or 2, with no side effects.

Summary

The following table summarises the effect of each transformation on the three important quantities. Individually, each transformation may violate invariants, but we are only interested in certain combinations of transformations which do not increase any of these quantities.

Effect of transformations

	Root degree	Total loss	Active roots
Active root reduction	$0{\text{ or }}{+}1$	$0$	$-1$
Root degree reduction	$-2$	$0$	$+1$
One node loss reduction	$+1$	${\text{at least }}{-}1$	$+1$
Two node loss reduction	$0$	$-1{\text{ or }}{-}2$	$0$

When deciding which transformations to perform, we consider only the worst case effect of these operations, for simplicity. The two types of loss reduction are also considered to be the same operation. As such, we define 'performing a loss reduction' to mean attempting each type of loss reduction in turn.

Worst case effect of transformations

	Root degree	Total loss	Active roots
Active root reduction	$+1$	$0$	$-1$
Root degree reduction	$-2$	$0$	$+1$
Loss reduction	$+1$	$-1$	$+1$

Implementation

Finding candidate nodes

The invariant restoring transformations rely on being able to find candidate nodes in $O(1)$ time. This means that we must keep track of active roots with the same rank, nodes with loss 1 of the same rank, and nodes with loss at least 2. There are several ways to do this.

The original paper by Brodal et al. described a fix-list and a rank-list.

Fix-list

The fix-list is divided into four parts:

1. Active roots ready for active root reduction – active roots with a partner of the same rank. Nodes with the same rank are kept adjacent.
2. Active roots not yet ready for active reduction – the only active roots for that rank.
3. Active nodes with loss 1 that are not yet ready for loss reduction – the only active nodes with loss 1 for that rank.
4. Active nodes that are ready for loss reduction – This includes active nodes with loss 1 that have a partner of the same rank, and active nodes with loss at least 2, which do not need partners to be reduced. Nodes with the same rank are kept adjacent.

To check if active root reduction is possible, we simply check if part 1 is non-empty. If it is non-empty, the first two nodes can be popped off and transformed. Similarly, to check if loss reduction is possible, we check the end of part 4. If it contains a node with loss at least 2, one node loss reduction is performed. Otherwise, if the last two nodes both have loss 1, and are of the same rank, two node loss reduction is performed.

Rank-list

The rank-list is a doubly linked list containing information about each rank, to allow nodes of the same rank to be partnered together in the fix-list.

For each node representing rank $r$ in the rank-list, we maintain:

• A pointer to the first active root in the fix-list with rank $r$. If such a node does not exist, this is NULL.
• A pointer to the first active node in the fix-list with rank $r$ and loss 1. If such a node does not exist, this is NULL.
• A pointer to the node representing rank $r+1$ and $r-1$, to facilitate the incrementation and decrementation of ranks.

The fix-list and rank-list require extensive bookkeeping, which must be done whenever a new active node arises, or when the rank or loss of a node is changed.

Shared flag

Using a shared flag to change make all nodes passive in $O(1)$ time

The merge operation changes all of the active nodes of the smaller heap into passive nodes. This can be done in $O(1)$ time by introducing a level of indirection. Instead of a boolean flag, each active node has a pointer towards an active flag object containing a boolean value. For passive nodes, it does not matter which active flag object they point to, as long as the flag object is set to passive, because it is not required to change many passive nodes into active nodes simultaneously.

Storing keys

The decrease-key operation requires a reference to the node we wish to decrease the key of. However, the decrease-key operation itself sometimes swaps the key of a node and the key root.

Assume that the insert operation returns some opaque reference that we can call decrease-key on. If these references are simply heap nodes, then by swapping keys we have mutated these references, causing mismatches. To ensure a key is always stays with the same reference, it is necessary to 'box' the key. Each heap node now contains a pointer to a box containing a key, and the box also has a pointer to the heap node. When inserting an item, we create a box to store the key in, link the heap node to the box both ways, and return the box object. To swap the keys between two nodes, we re-link the pointers between the boxes and nodes instead.

Operations

Merge

Let $h_{1}$ and $h_{2}$ be strict Fibonacci heaps, where $n_{1}=|h_{1}|\leq |h_{2}|=n_{2}$. If either is empty, return the other. Henceforth, assume $h_{1}$ and $h_{2}$ are both non-empty. Since the size of the fix-list and rank-list of each heap is logarithmic with respect to the size of the heap, we cannot possibly merge these auxilliary structures in constant time. Instead, we throw away the structure of the smaller heap $h_{1}$ by discarding its fix-list and rank-list, and converting all of its nodes into passive nodes. This can be done in constant time, with a shared flag, as shown above. Link $h_{1}$ and $h_{2}$, letting the root with the smaller key become the parent of the other. Let $Q_{1}$ and $Q_{2}$ be the queues of $h_{1}$ and $h_{2}$ respectively. Their combined queue is $Q=Q_{1}+\{r_{\mathrm {larger} }\}+Q_{2}$, where $r_{\mathrm {larger} }$ is the root with the larger key.

The only possible structural violation is the root degree. This is solved by performing 1 active root reduction, and 1 root degree reduction, if each transformation is possible.

	Root degree	Total loss	Active roots
State after merge	$+1$	$0$	$0$
$1\times$Active root reduction	$+1$	$0$	$-1$
$1\times$Root degree reduction	$-2$	$0$	$+1$
Total	$0$	$0$	$0$

Proof of correctness

Invariants 1, 2, and 3 hold automatically, since the structure of the heap is discarded. As calculated above, any violations of invariant 4 are solved by the root degree reduction transformation.

To verify invariant 5, we consider the final positions of nodes in $Q$. Each node has its degree bounded by $2\lg(2n-p)+10$ or $2\lg(2n-p)+9$.

For the smaller heap $h_{1}$ the positions in $Q_{1}$ are unchanged. However, all nodes in $h_{1}$ are now passive, which means that their constraint may change from the $+10$ case to the $+9$ case. But noting that $n_{1}\leq n_{2}$, the resulting size $n=n_{1}+n_{2}$ is at least double $n_{1}$. This results in an increase of at least 1 on each constraint, which eliminates the previous concern.

The root with the larger key between $h_{1}$ and $h_{2}$ becomes a non-root, and is placed between $Q_{1}$ and $Q_{2}$ at position $n_{1}$. By invariant 4, its degree was bounded by either $R_{1}+3=2\lg n_{1}+9$ or $R_{2}+3=2\lg n_{2}+9$, depending on which heap it came from. It is easy to see that this is less than $2\lg {(2n_{1}+2n_{2}-n_{1})}+9$ in any case.

For the larger heap, the positions increase by $n_{1}$. But since the resulting size is $n=n_{1}+n_{2}$, the value $2n-p$ actually increases, weakening the constraint.

Insert

Insertion can be considered a special case of the merge operation. To insert a single key, create a new strict Fibonacci heap containing a single passive node and an empty queue, and merge it with the main heap.

Find-min

Due to the minimum-heap property, the node with the minimum key is always at the root, if it exists.

Delete-min

If the root is the only node in the heap, we are done by simply removing it. Otherwise, search the children of the root to find the node $x$ with minimum key, and set the new root to $x$. If $x$ is active, make it passive, causing all active children of $x$ to implicitly become active roots. Link the children of the old root to $x$. Since $x$ is now the root, move all of its passive linkable children to the right, and remove $x$ from $Q$.

The degree of the root approximately doubles, because we have linked all the children of the old root to $x$. We perform the following restorative transformations:

1. Repeat twice: rotate $Q$ by moving the head $y$ of $Q$ to the back. If the two rightmost children of $y$ are passive, link them to the root.
2. If a loss reduction is possible, perform it.
3. Perform active root reductions and root degree reductions until neither is possible.

To see how step 3 is bounded, consider the state after step 3:

Stage of delete-min	Root degree	Total loss	Active roots
State after delete-min	$+R+6$	$0$	$+R$
$2\times$Queue rotation	$+4$	$0$	$0$
$1\times$Loss reduction	$+1$	$-1$	$+1$
Total	$+R+11$	$-1$	$+R+1$

Observe that, 3 active root reductions and 2 root reductions decreases the root degree and active roots by 1:

	Root degree	Total loss	Active roots
$3\times$Active root reduction	$+3$	$0$	$-3$
$2\times$Root degree reduction	$-4$	$0$	$+2$
Total	$-1$	$0$	$-1$

Since $R=2\lg n+6$, step 3 never executes more than $O(\log n)$ times.

Proof of correctness

Invariant 1 holds, since no active roots are created.

The size of the heap $n$ decreases by 1, causing $R=2\lg n+6$ to decrease by no more than 1. The total loss is required to satisfy $L\leq R+1$ for invariant 3, and by performing a loss reduction we have guaranteed no violations.

We show that invariant 2 holds by contradiction. Assume that invariant 2 is broken, with more than $R+1$ active roots present. From corollary 2, the maximum rank of a node is $R$. By the pigeonhole principle, there exists a pair of active roots with the same rank. However, step 4 already ensures that no such pair of active roots exists, so invariant 2 holds.

To show invariant 4 holds, we again proceed by contradiction. Let the degree of the root be $\geq R+4$. The children of the root fall into three categories: active roots, passive non-linkable nodes, and passive linkable nodes. Each passive non-linkable node subsumes an active root, since its subtree is not all passive. By invariant 3, the number of active roots is at most $R+1$, which means that the rightmost three children of the root must be passive linkable. Since this is precisely the prerequisite for root degree reduction, which has already been exhaustively applied, invariant 4 holds.

The constraints imposed by invariant 5 strengthen, because the heap size $n$ has decreased by 1. Because the first 2 nodes in $Q$ are popped in step 1, the positions of the other elements in $Q$ decrease by 2. Therefore, the degree constraints $2\lg(2n-p)+10$ and $2\lg(2n-p)+9$ remain constant for these nodes. The two nodes which were popped previously had positions 1 and 2 in $Q$, and now have positions $n-2$ and $n-1$ respectively, because $Q$ contains all of the $n-1$ non-root nodes. The effect is that their degree constraints have strengthed by 2, however, we cut off two passive children, which is sufficient to satisfy the constraint.

Decrease-key

Let $x$ be the node whose key has been decreased. If $x$ is the root, we are done. Otherwise, detach the subtree rooted at $x$, and link it to the root. If the key of $x$ is smaller than the key of the root, swap their keys.

Up to three structural violations may have occurred. Firstly, the degree of the root has increased (unless $x$ was already a child of the root). The second violation may have occured when $x$ was detached from its original parent $y$.

• If $x$ is passive, then there are no extra violations.
• If $x$ was previously an active root with $y$ passive, then moving $x$ from being a child of $y$ to a child of the root does not create any additional active roots, nor does it increase the loss of any node.
• If both $x$ and $y$ are active, then the loss of $y$ increases by 1, and an extra active root is created (by linking $x$ to the root).

In the worst case, all three quantities (root degree, total loss, active roots) increase by 1.

After performing 1 loss reduction, the worst case result is still that the root degree and number of active roots have both increased by 2. Again, we use the fact that 3 active root reductions and 2 root reductions decreases both of these quantities by 1. Applying these transformations 6 and 4 times respectively is sufficient to eliminate all violations.

	Root degree	Total loss	Active roots
State after decrease-key	$+1$	$+1$	$+1$
$1\times$Loss reduction	$+1$	$-1$	$+1$
$6\times$Active root reduction	$+6$	$0$	$-6$
$4\times$Root degree reduction	$-8$	$0$	$+4$
Total	$0$	$0$	$0$

Proof of correctness

Invariant 1 is unaffected, because the root is passive, and the nodes which were previously the left siblings of $x$ move to fill the gap left by $x$. Invariant 5 trivially holds as $Q$ is unchanged.

We apply the pigeonhole principle again, to show that invariant 3 is satisfied. Assume that the total loss is such that $L>R+1$. Because the maximum rank is $R$, either there either exists a pair of active nodes with equal rank and loss 1, or an active node with loss $\geq 2$. Both cases present an opportunity for loss reduction, which is applied immediately.

As described in the proof for delete-min, any violation of invariant 2 guarantees the availability of an active root reduction by the pigeonhole principle, and any violation of invariant 4 guarantees the availability of a root degree reduction.

Applications

Although they are theoretically optimal, strict Fibonacci heaps are not practical to use. There are extremely complicated to implement, requiring management of more than 10 pointers per node. Despite being relatively simpler than the Brodal queue, experiments show that in practice the strict Fibonacci heap performs slower than the Brodal queue and also slower than ordinary Fibonacci heaps However, the Brodal queue makes extensive use of extendable arrays and redundant counters, whereas the strict Fibonacci heap is pointer based only.

Summary of running times

Here are time complexities of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.

Operation	find-min	delete-min	decrease-key	insert	meld	make-heap
Binary	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)	Θ(n)
Skew	Θ(1)	O(log n) am.	O(log n) am.	O(log n) am.	O(log n) am.	Θ(n) am.
Leftist	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)
Binomial	Θ(1)	Θ(log n)	Θ(log n)	Θ(1) am.	Θ(log n)	Θ(n)
Skew binomial	Θ(1)	Θ(log n)	Θ(log n)	Θ(1)	Θ(log n)	Θ(n)
2–3 heap	Θ(1)	O(log n) am.	Θ(1)	Θ(1) am.	O(log n)	Θ(n)
Bottom-up skew	Θ(1)	O(log n) am.	O(log n) am.	Θ(1) am.	Θ(1) am.	Θ(n) am.
Pairing	Θ(1)	O(log n) am.	o(log n) am.	Θ(1)	Θ(1)	Θ(n)
Rank-pairing	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Fibonacci	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Strict Fibonacci	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)
Brodal	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)

External links

• JavaScript simulation of strict Fibonacci heap