In computer science, a strict Fibonacci heap is a priority queue data structure with low worst case time bounds. It matches the amortized time bounds of the Fibonacci heap in the worst case. To achieve these time bounds, strict Fibonacci heaps maintain several invariants by performing restoring transformations after every operation. These transformations can be done in constant time by using auxiliary data structures to track invariant violations, and the pigeonhole principle guarantees that these can be fixed. Strict Fibonacci heaps were invented in 2012 by Gerth S. Brodal, George Lagogiannis, and Robert E. Tarjan, with an update in 2025.
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 elements by performing insertions and delete-min operations. However, strict Fibonacci heaps are simpler than Brodal queues, which make use of dynamic arrays and redundant counters, whereas the strict Fibonacci heap is pointer based only.
Structure
A strict Fibonacci heap is a single tree satisfying the minimum-heap property. That is, the key of a node is always smaller than or equal to its children. As a direct consequence, the node with the minimum key always lies at the root.
Like ordinary Fibonacci heaps, strict Fibonacci heaps possess substructures similar to binomial heaps. To identify these structures, we label every node with one of two types. We thus introduce the following definitions and rules:
All nodes are either active (colored white) or passive (colored red). 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. For any node, the active children lie to the left of the passive children. An active root always has zero loss. The root is passive. The passive linkable children of the root lie to the right of the passive non-linkable children.
Invariants Invariant 1: Structure The th rightmost active child of an active node satisfies .
Thus, the loss of an active node can be viewed as a generalisation of Fibonacci heap 'marks'. For example, a subtree consisting of only active nodes with loss zero is a binomial tree.
In addition, several invariants which impose logarithmic bounds on three main quantities: the number of active roots, the total loss, and the degrees of nodes. This is in contrast to the ordinary Fibonacci heap, which is more flexible and allows structural violations to grow on the order of to be cleaned up later, as it is a lazy data structure.
To assist in keeping the degrees of nodes logarithmic, every non-root node also participates in a queue . In the following section, and for rest of this article, we define the real number , where is the number of nodes in the heap, and denotes the binary logarithm.
Invariant 2: Active roots The total number of active roots is at most .
Invariant 3: Total loss The total loss in the heap is at most .
Invariant 4: Root degree The degree of the root is at most .
Invariant 5: Non-root degrees For an active node with zero loss, the degree is at most , where is its position in (with 1 as the first element). For all other non-root nodes, the degree is at most .
Corollary 1: Maximum degree The degree of any non-root node is at most .
Proof: This follows immediately from invariant 5. Letting , we have
Lemma 1: Maximum rank If invariant 1 holds, the maximum rank or any active node is at most , where is the total loss.
Proof: We proceed by contradiction. Let be an active node with maximal rank in a heap with nodes and total loss , and assume that , where is the smallest integer such that . Our goal is to show that the subtree rooted at contains nodes, which is a contradiction because there are only nodes in the heap.
Discard all subtrees rooted at passive nodes from , leaving it with only active nodes. Cut off all the grandchildren of whose subtrees contain any node of positive loss, and increase the loss of the children of accordingly, once for each grandchild lost. The quantity is unchanged for the remaining nodes, preserving invariant 1. Furthermore, the total loss is still at most .
The children of now consists of loss-free subtrees and leaf nodes with positive loss. Currently, satisfies for the th rightmost child of . We make this an exact equality by first reducing the loss of each , and pruning any grandchildren if necessary. Afterwards, exactly. All other descendants of are also converted into binomial subtrees by pruning children as necessary.
We now attempt to reconstruct a minimal version of by starting with a binomial tree of degree , containing active nodes. We wish to increase the loss to , but keep the rank of as and the number of nodes as low as possible. For a binomial tree of degree , there is one child of each degree from to . Hence, there are grandchildren of order . If we cut all the grandchildren whose degree , then we have cut grandchildren, which is sufficient to bring the loss up to . All grandchildren with degree survive. Let be the child of with degree and loss 0. By assumption, , and is a complete binomial tree, so it has at least nodes. Since this would mean has at least nodes, we have reached a contradiction, and therefore . Noting that , we obtain .
Corollary 2: Maximum rank If invariants 1 and 3 both hold, then the maximum rank is .
Proof: From invariant 3, we have . By substituting this into lemma 1, we calculate as follows:
Transformations The following transformations restore the above invariants after a priority queue operation has been performed. There are three main quantities we wish to minimize: the number of active roots, the total loss in the heap, and the degree of the root. All transformations can be performed in time, which is possible by maintaining auxiliary data structures to track candidate nodes (described in the section on implementation).
Active root reduction Let and be active roots with equal rank , and assume . Link as the leftmost child of and increase the rank of by 1. If the rightmost child of is passive, link to the root.
As a result, 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,
Since becomes the th rightmost child of , and has rank , invariant 1 is preserved.
Lemma 2: Availability of active root reduction If invariant 2 is violated, but invariants 1 and 3 hold, then active root reduction is possible. Proof: Because invariant 2 is broken, there are more than active roots present. From corollary 2, the maximum rank of a node is . By the pigeonhole principle, there exists a pair of active roots with the same rank.
Loss reduction
One node loss reduction Let be an active non-root with loss at least 2. Link to the root, thus turning it into an active root, and resetting its loss to 0. Let the original parent of be . must be active, since otherwise would have previously been an active root, and thus could not have had positive loss. The rank of is decreased by 1. If 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 preferable to two node loss reduction, but still a necessary operation.
Two node loss reduction Let and be active nodes with equal rank and loss equal to 1, and let be the parent of . Without loss of generality, assume that . Detach from , and link to . Increase the rank of by 1 and reset the loss of and from 1 to 0.
must be active, since had positive loss and could not have been an active root. Hence, the rank of is decreased by 1. If is not an active root, increase its loss by 1.
Overall, the total loss decreases by either 1 or 2, with no side effects.
Lemma 3: Availability of loss reduction If invariant 3 is violated by 1, but invariant 2 holds, then loss reduction is possible. Proof: We apply the pigeonhole principle again. If invariant 3 is violated by 1, the total loss is . Lemma 1 can be reformulated to also work with . Thus, corollary 2 holds. Since the maximum rank is , either there either exists a pair of active nodes with equal rank and loss 1, or an active node with . Both cases present an opportunity for loss reduction.
Root degree reduction
Let , , and be the three rightmost passive linkable children of the root. Detach them all from the root and sort them such that . Change and to be active. Link to , link to , and link as the leftmost child of the root. As a result, becomes an active root with rank 1 and loss 0. The rank and loss of 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.
Lemma 4: Availability of root degree reduction If invariant 4 is violated, but invariant 2 holds, then root degree reduction is possible. Proof: If invariant 4 is broken, then the degree of the root is at least . 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 contains at least one active node. Because the number of active roots is at most , the rightmost three children of the root must therefore be passive linkable.
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 transformationsActive rootsTotal lossRoot degreeActive root reductionRoot degree reductionOne node loss reductionTwo node loss reduction
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 transformationsActive rootsTotal lossRoot degreeActive root reductionRoot degree reductionLoss reduction
Implementation
Linking nodes To ensure active nodes lie to the left of passive nodes, and preserve invariant 1, the linking operation should place active nodes on the left, and passive nodes on the right. It is necessary for active and passive nodes to coexist in the same list, because the merge operation changes all nodes in the smaller heap to be passive. If they existed in two separate lists, the lists would have to be concatenated, which cannot be done in constant time for all nodes.
For the root, we also pose the requirement that passive linkable children lie to the right of the passive non-linkable children. Since we wish to be able link nodes to the root in constant time, a pointer to the first passive linkable child of the root must be maintained.
Finding candidate nodes The invariant restoring transformations rely on being able to find candidate nodes in 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.
The original paper by Brodal et al. described a fix-list and a rank-list as a way of tracking candidate nodes.
Fix-list
The fix-list is divided into four parts: