Strict Fibonacci heap

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a strict Fibonacci heap is a <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a> data structure with low <a href="/facts/Worst-case_complexity/kqzQkwIc">worst case</a> time bounds. It matches the <a href="/facts/Amortized_analysis/9fFYenJz">amortized</a> time bounds of the <a href="/facts/Fibonacci_heap/4cJIHkNQ">Fibonacci heap</a> in the worst case. To achieve these time bounds, strict Fibonacci heaps maintain several <a href="/facts/Invariant_(computer_science)/9TeNN2ed">invariants</a> 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 <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a> guarantees that these can be fixed. Strict Fibonacci heaps were invented in 2012 by <a href="/facts/Gerth_St%25C3%25B8lting_Brodal/p2dUcm7P">Gerth S. Brodal</a>, George Lagogiannis, and <a href="/facts/Robert_Tarjan/kn1pMCN0">Robert E. Tarjan</a>, with an update in 2025.
Along with <a href="/facts/Brodal_queue/3NzyhnJn">Brodal queues</a>, strict Fibonacci heaps belong to a class of <a href="/facts/Asymptotically_optimal_algorithm/fnfvbMYE">asymptotically optimal</a> 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 <a href="/facts/Sorting_algorithm/PwHpj1Gs">sort</a> 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 <a href="/facts/Dynamic_array/EtocbTWK">dynamic arrays</a> and redundant counters, whereas the strict Fibonacci heap is <a href="/facts/Pointer_machine/0SdkYhF2">pointer based</a> only.

Strict Fibonacci heap open-in-new

Strict Fibonacci heap