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.

[1] All operations on strict Fibonacci heaps run in worst case constant time except delete-min, which is necessarily logarithmic.

[2] However, strict Fibonacci heaps are simpler than Brodal queues, which make use of dynamic arrays and redundant counters,[3] whereas the strict Fibonacci heap is pointer based only.

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

As a direct consequence, the node with the minimum key always lies at the root.

We thus introduce the following definitions and rules: 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

The following transformations restore the above invariants after a priority queue operation has been performed.

time, which is possible by maintaining auxiliary data structures to track candidate nodes (described in the section on implementation).

The net change of this transformation is that the degree of the root node decreases by 2.

When deciding which transformations to perform, we consider only the worst case effect of these operations, for simplicity.

The invariant restoring transformations rely on being able to find candidate nodes in

The original paper by Brodal et al. described a fix-list and a rank-list as a way of tracking candidate nodes.

The decrease-key operation requires a reference to the node we wish to decrease the key of.

Assume that the insert operation returns some opaque reference that we can call decrease-key on, as part of the public API.

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.

Insertion can be considered a special case of the merge operation.

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

is now the root, move all of its passive linkable children to the right, and remove

Hence, applying these transformations 6 and 4 times respectively is sufficient to eliminate all violations.

Although theoretically optimal, strict Fibonacci heaps are not useful in practical applications.

They are extremely complicated to implement, requiring management of more than 10 pointers per node.

[7] Despite being relatively simpler, experiments show that in practice the strict Fibonacci heap performs slower than the Brodal queue.