Strict Fibonacci heap

Strict Fibonacci heap
Type	Heap
Invented	2012
Invented by	Gerth S. Brodal, George Lagogiannis, and Robert E. Tarjan
Complexities in big O notation
Space complexity Time complexity Function Amortized Worst case Insert Θ(1) Find-min Θ(1) Delete-min O(log n) Decrease-key Θ(1) Merge Θ(1)

In computer science, a strict Fibonacci heap is a priority queue data structure with worst case time bounds equal to the amortized bounds of the Fibonacci heap. 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 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$ elements by performing $n$ insertions and $n$ delete-min operations. Strict Fibonacci heaps were invented in 2012 by Gerth Stølting Brodal, George Lagogiannis, and Robert E. Tarjan.

Structure

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

The nodes in the heap have the following rules:

• All nodes are either active (colored white) or passive (colored red).
• The root is passive.
• For any node, the active children lie to the left of the passive children.

We also make the following definitions:

• 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 children it has lost, including active and passive children.
• The loss of an active root is always 0 (similar to how ordinary Fibonacci heap roots are always unmarked).

To facilitate root degree reduction (described below), the passive linkable children of the root always lie to the right of the passive non-linkable children.

Invariants

Intuitively, active nodes are the only nodes which have some kind of order, whilst passive nodes do not have any particular order. This is governed by the following structural invariant:

• For an active node, the $i$th rightmost active child $c_{i}$ (zero-indexed) satisfies $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i$.

This invariant leads to similar structures found in binomial heaps and ordinary fibonacci heaps. For example, a subtree composed entirely of active nodes with no loss is a binomial tree.

The logarithmic bound of the delete-min operation is guaranteed by several additional invariants. A queue of all non-root nodes is also maintained

In the following, let the real number $R$ be defined as $2\lg n+6$, where $n$ is the number of nodes in the heap, and $\lg$ denotes the binary logarithm.

• The total loss in the heap is at most $R+1$.
• The total number of active nodes is at most $R+1$.
• The degree of the root is at most $R+3$.
• For an active node with loss 0, its degree is bounded by $2\lg(2n-p)+10$, and for all other nodes, $2\lg(2n-p)+9$.
• (Corallary) The degree of any non-root node is at most $R+6$. (Proof: let $p$ = 0 in the previous invariant.)

Transformations

The following four transformations are intended to restore the above invariants after a priority queue operation has been performed. All transformations can be performed in $O(1)$ time, which is possible by maintaining some auxilliary data structure to track candidate nodes (see section on implementation).

Active root reduction

Let $x$ and $y$ be active roots with equal rank $r$, and assume $x.\mathrm {key} \leq y.\mathrm {key}$. Link $y$ to $x$ and increase the rank of $x$ by 1. If the rightmost child $z$ of $x$ is passive, link $z$ to the root.

Root degree reduction

Let $x$, $y$, and $z$ be the three rightmost passive linkable children of the root. Detach them all from the root. Sort them such that $x.\mathrm {key} \leq y.\mathrm {key} \leq z.\mathrm {key}$. Change $x$ and $y$ to be active. Link $z$ to $y$, $y$ to $x$, and $x$ to the root. As a result, $x$ becomes an active root with rank 1 and loss 0. The rank and loss of $y$ 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. However, this operation is always applied in conjunction with active root reduction.

One node loss reduction

Let $x$ be an active non-root with loss at least 2. Link $x$ to the root, thus turning it into an active root, and resetting its loss to 0. Let the original parent of $x$ be $y$. $y$ must be active, since otherwise $x$ would have previously been an active root, and thus could not have had positive loss. The rank of $y$ is decreased by 1. If $y$ 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 preferrable to two node loss reduction, but still a necessary operation.

Two node loss reduction

Let $x$ and $y$ be active nodes with equal rank $r$ and loss equal to 1, and let $z$ be the parent of $y$. Without loss of generality, assume that $x.\mathrm {key} \leq y.\mathrm {key}$. Detach $y$ from $z$, and link $y$ to $x$. Increase the rank of $x$ by 1 and reset the loss of $x$ and $y$ from 1 to 0.

$z$ must be active, since $y$ had positive loss and could not have been an active root. Hence, the rank of $z$ is decreased by 1. If $z$ is not an active root, increase its loss by 1.

Overall, the total loss decreases by 1 or 2.

Summary

The table below presents the effect of these transformations on the three main quantities we wish to minimise.

Effect of transformations

	Root degree	Total loss	Active roots
Active root reduction	$0{\text{ or }}{+}1$	$0$	$-1$
Root degree reduction	$-2$	$0$	$+1$
One node loss reduction	$+1$	${\text{at least }}{-}1$	$+1$
Two node loss reduction	$0$	$-1{\text{ or }}{-}2$	$0$

However, 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 considered to be the same operation, thus, to perform a 'loss reduction' means to attempt each type of loss reduction in turn.

Worst case effect of transformations

	Root degree	Total loss	Active roots
Active root reduction	$+1$	$0$	$-1$
Root degree reduction	$-2$	$0$	$+1$
Loss reduction	$+1$	$-1$	$+1$

Implementation

Finding candidate nodes

The invariant restoring transformations rely on being able to find candidate nodes in $O(1)$ 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. There are several ways to do this.

The original paper by Brodal et al. used a fix-list and a rank-list.

The fix-list is divided into four parts:

1. Active roots ready for active root reduction – active roots with at least 1 partner of the same rank. Nodes with the same rank are kept adjacent.
2. Active roots not yet ready for active reduction – the only active roots for that rank.
3. Active nodes with loss 1 that are not yet ready for loss reduction – the only active nodes with loss 1 for that rank.
4. 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.

Active nodes with loss 0 are not included in the fix-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 $r$ in the rank-list, we maintain:

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

Shared pointers

The merge operation changes all of the active nodes of the smaller heap into passive nodes. This can be done in $O(1)$ time by using a shared pointer. Instead of a boolean flag, each active node has a pointer towards an active flag object containing a boolean value. For passive nodes, it does not matter which active flag object they point to, because it is not required to change passive nodes to active en masse.

Operations

Merge

Let $h_{1}$ and $h_{2}$ be strict Fibonacci heaps, where $|h_{1}|\leq |h_{2}|$. If either is empty, return the other and we are done. Assuming $h_{1}$ and $h_{2}$ are both non-empty, merging their fix-lists and rank-lists would take logarithmic time. Instead, we throw away the structure of the smaller heap $h_{1}$ by discarding its fix-list and rank-list, and converting all of its nodes into passive nodes. This can be done in constant time, with a shared pointer, as shown above. Link $h_{1}$ and $h_{2}$, letting the root with the smaller key become the parent of the other. Let $q_{1}$ and $q_{2}$ be the queues of $h_{1}$ and $h_{2}$ respectively. The combined queue is $q_{1}+\{r_{\mathrm {larger} }\}+q_{2}$, where $r_{\mathrm {larger} }$ is the root with the larger key.

The only possible structural violation is the root degree. This is solved by performing 1 active root reduction, and 1 root degree reduction, if each transformation is possible.

	Root degree	Total loss	Active roots
State after merge	$+1$	$0$	$0$
$1\times$Active root reduction	$+1$	$0$	$-1$
$1\times$Root degree reduction	$-2$	$0$	$+1$
Total	$0$	$0$	$0$

Insert

Insertion can be considered a special case of the merge operation. Create a new strict Fibonacci heap with a single passive node, and empty queue. Merge it with the main heap.

Find-min

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

Delete-min

If the root is the only node in the heap, we are done by simply removing it. Otherwise, search the children of the root to find the next node with minimum key, $x$. If $x$ is active, make it passive and set the new root to $x$. All active children of $x$ thus become active roots. Since $x$ is now the root, move all of its passive linkable children to the right. Link all children from the old root to $x$.

Decrease-key

Let $x$ be the node whose key has been decreased. If $x$ is the root, we are done. Otherwise, detach the subtree rooted at $x$, and link it to the root. If the key of $x$ is smaller than the key of the root, swap their keys.

Up to two structural violations may have occurred. Firstly, the degree of the root has increased (unless $x$ was already a child of the root). The second violation may have occured when $x$ was detached from its parent $y$.

• If $x$ was previously an active root, then moving $x$ from being a child of $y$ to a child of the root does not create any additional active roots, nor does it increase the loss of any node.
• If $x$ is passive and $y$ is passive, then there are no extra violations.
• If $x$ is passive and $y$ is active, then the loss of $y$ increases by 1, which may violate the total loss invariant.
• If both $x$ and $y$ are passive, then the loss of increases by 1, and an extra active root is created (by linking $x$ to the root).

In the worst case, all three quantities (root degree, total loss, active roots) increase by 1.

After performing 1 loss reduction, 6 active root reductions and 4 root degree reductions (in alternation) are sufficient to fix all structural violations, although not all will be required.

	Root degree	Total loss	Active roots
State after decrease-key	$+1$	$+1$	$+1$
$1\times$Loss reduction	$+1$	$-1$	$+1$
$6\times$Active root reduction	$+6$	$0$	$-6$
$4\times$Root degree reduction	$-8$	$0$	$+4$
Total	$0$	$0$	$0$

Proof of bounds

The performance of the delete-min operation depends on the degree of the root. Unlike ordinary Fibonacci heaps, the number of structural violations in a strict Fibonacci heap is kept bounded. By applying the pigeonhole principle, structural violations can be detected and fixed in constant time.

Considerations

Although they are theoretically optimal, strict Fibonacci heaps are not practical to use. Despite having simpler structure, experiments show that in practice the strict Fibonacci heap performs slower than more complicated Brodal queue and also slower than ordinary Fibonacci heaps.

Summary of running times

Here are time complexities of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.

Operation	find-min	delete-min	decrease-key	insert	meld	make-heap
Binary	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)	Θ(n)
Skew	Θ(1)	O(log n) am.	O(log n) am.	O(log n) am.	O(log n) am.	Θ(n) am.
Leftist	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)
Binomial	Θ(1)	Θ(log n)	Θ(log n)	Θ(1) am.	Θ(log n)	Θ(n)
Skew binomial	Θ(1)	Θ(log n)	Θ(log n)	Θ(1)	Θ(log n)	Θ(n)
2–3 heap	Θ(1)	O(log n) am.	Θ(1)	Θ(1) am.	O(log n)	Θ(n)
Bottom-up skew	Θ(1)	O(log n) am.	O(log n) am.	Θ(1) am.	Θ(1) am.	Θ(n) am.
Pairing	Θ(1)	O(log n) am.	o(log n) am.	Θ(1)	Θ(1)	Θ(n)
Rank-pairing	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Fibonacci	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Strict Fibonacci	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)
Brodal	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)

External links

• JavaScript simulation of strict Fibonacci heap