Strict Fibonacci heap

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 or passive '.
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.
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
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
; Invariant 3: Total loss
; Invariant 4: Root degree
; Invariant 5: Non-root degrees
; Corollary 1: Maximum degree
; Lemma 1: Maximum rank
; Corollary 2: Maximum rank

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.

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

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

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

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.

	Active roots	Total loss	Root degree
Active root reduction
Root degree reduction
One node loss reduction
Two 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.

	Active roots	Total loss	Root degree
Active root reduction
Root degree reduction
Loss 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:

Active roots ready for active root reduction – active roots with a partner of the same rank. Nodes with the same rank are kept adjacent.
Active roots not yet ready for active reduction – the only active roots for that rank.
Active nodes with loss 1 that are not yet ready for loss reduction – the only active nodes with loss 1 for that rank.
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 in the rank-list, we maintain:

A pointer to the first active root in the fix-list with rank. If such a node does not exist, this is NULL.
A pointer to the first active node in the fix-list with rank and loss 1. If such a node does not exist, this is NULL.
A pointer to the node representing rank and, 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.