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 n {\displaystyle n} elements by performing n {\displaystyle n} insertions and n {\displaystyle n} 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 i {\displaystyle i} th rightmost active child c i {\displaystyle c_{i}} of an active node satisfies c i . r a n k + c i . l o s s ≥ i − 1 {\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1} . 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 O ( n ) {\displaystyle O(n)} 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 Q {\displaystyle Q} . In the following section, and for rest of this article, we define the real number R = 2 lg n + 6 {\displaystyle R=2\lg n+6} , where n {\displaystyle n} is the number of nodes in the heap, and lg {\displaystyle \lg } denotes the binary logarithm.
Invariant 2: Active roots The total number of active roots is at most R + 1 {\displaystyle R+1} . Invariant 3: Total loss The total loss in the heap is at most R + 1 {\displaystyle R+1} . Invariant 4: Root degree The degree of the root is at most R + 3 {\displaystyle R+3} . Invariant 5: Non-root degrees For an active node with zero loss, the degree is at most 2 lg ( 2 n − p ) + 10 {\displaystyle 2\lg(2n-p)+10} , where p {\displaystyle p} is its position in Q {\displaystyle Q} (with 1 as the first element). For all other non-root nodes, the degree is at most 2 lg ( 2 n − p ) + 9 {\displaystyle 2\lg(2n-p)+9} . Corollary 1: Maximum degree The degree of any non-root node is at most R + 6 {\displaystyle R+6} . Proof: This follows immediately from invariant 5. Letting p = 0 {\displaystyle p=0} , we have
2 lg ( 2 n − 0 ) + 10 = 2 lg n + 12 = R + 6 {\displaystyle 2\lg(2n-0)+10=2\lg n+12=R+6}
… excerpt ends here. Continue reading the full article.
