Quake Heap

Quake Heap [1] is a min heap (or max heap) that supports the following operations:

with $O(n)$ space. For comparison based min heap, either $insert(x)$ or delete-min() takes $O(\log n)$ amortized time. Otherwise, we would have an $o(n \log n)$ comparison based sorting algorithm.

In this blog we walk through its construction step by step and illustrate the philosophy behind. Some of the ideas also appear in other designs of min heaps.

Insertion

For insertion we are going to be lazy. Consider inserting the elements 1, 2, 3, 4, 5 into the heap. For each insertion, we just create a singleton node while maintaining a pointer (the "min-pointer") to the minimum node. The picture below shows the heap we obtain after five insertions. Each insertion has time complexity $O(1)$.

Deletion and Binomial Heap

It would be easier to consider the case delete-min() without decrease-key(x) first. Now we try to delete the minimum element from heap. The first step, of course, is to remove the element $1$, after which we get the following heap.

Here comes the problem. The "min-pointer" is removed along with the deletion. To maintain it, it seems that we need to loop over the entire list to update the min, which takes $O(n)$ time. If we do nothing else than merely scanning all elements, we need another $O(n)$-scanning for the next deletion. We hope that the comparison performed for the current delete-min operation can reduce the ones we need to perform in the future.

The idea is to merge the elements into trees. Intuitively, the trees "remember" the comparison performed before and save us from comparing the same pairs again.

Various tree structure can be used to record the comparison and this may result in the design of different data structure. The one picked by Quake heap is the tournament tree. It only compares and merges (linking) two trees of the same height. A new node is created as the root of the two trees. The new node's value equals to the smaller one of the roots of the two trees.

For example, in the following example, both the node 4 and 5 are viewed as trees with height one. We can compare and link the two trees. A new node with value 4 (the smaller value between 4 and 5) is created as the new root of the merged tree.

We can continue to link node 3 and 2.

The linking is performed recursively. Noting the the current two trees have the same height, we link them. We need to also update the "min-pointer" during the linking.

The construction takes $O(n)$ time. But we can charge the cost of these link operations into the creation of the trees' roots before. We have performed 3 link operations for the four nodes each being the root of a singleton tree. On average, we pay $O(1)$ per operation. To make the amortized argument more vivid, we can think that conceptually we an additional coin for each singleton tree creation. Therefore, before linking, we have four coins as follows:

Merging node 5 and 4 has actual cost $O(1)$ and creates a new tree root. We use the coin of node 5 to pay the actual cost. Element 4 is the new root and it still has a coin. By using the coin idea, we charge (or averaging) the cost of this link operation to the cost of the creation of node 5.

Merging node 3 and 2 uses one coin. We use the coin reserved by node 3. After this, the elements 4 and 2 (the elements that are roots of some trees) still have a coin.

Merging the two trees left uses one coin. We use the coin reserved by node 4. After this, the element 2 is still a root and still has a coin.

In general, we may need to pay more than $O(1)$ for delete-min(). Consider we would like to perform the operation for the following.

We need to remove all nodes on a root-to-leaf path. In this example it is the path that contains element 2.

After the removal, some children of the nodes in this root-to-leaf path are now exposed as tree roots. In this example, node 4 and 3 are tree roots. We need to reserve two coins node 4 and 3. The coins are reserved for potential linking performed in the future.

Finally we need to compare and link any two trees of the same height, in a recursive manner. This part is paid by the coins reserved for the tree roots.

To analyze the amortized running time of delete-min(), we define the height of the tree as $H$. We need to remove $H$ nodes from the root-to-leaf path, expose $\max \{H - 1, 0 \}$ node as tree roots and reserve coins for them, followed by recursively linking two trees with the same height. The final step is "free" and covered by the coins reserved. Therefore the amortized cost is $H + \max \{H - 1, 0\} = \max \{ 2H - 1, H \} \le 2H$.

Key Observation:

To bound the time of delete-min() to $O(\log n)$, it is critical to control the size of $H$.

To analyze how large $H$ could be, we study how it grow. Initially, a tree with $H = 1$ contains only 1 key. When we link two trees with $H = 1$, the new tree has height $H = 2$ and $2$ keys (although it has $3$ nodes). In general, a tree with height $H = h$ contains $2^{h - 1}$ keys and this can be easily proved by induction.

If there is no decrease-key operation, the tree with height $h$ has $2^{h - 1}$ keys and $2^h - 1$ nodes. As there are at most $n$ keys, the maximum possible height, denoted as $H$, is bounded by $\log n$.

The heap we have constructed so far has a special name called "Binomial Heap".

Decrease-Key

If there is only insert() and decrease-key() operation, min heap is easy to implemented. We can use a linked list / dynamic array, while maintaining the min pointer / min index.

If we need to incorporate delete-min() operation, the decrease-key(x) itself is still easy, while the former requires significant modification. For decrease-key(x), we adopt a lazy strategy. If after decreasing, $x$'s value is still smaller than its parent (or $x$ is the root of the tree and has no parent), then everything is fine. For example, if we decrease $4$ to $3.5$ (the node 4 has parent 2), then we do not need to modify the tree after the operation.

On the other hand, if we decrease 4 to 1, then its value is smaller than its parent 2.

We need to detach the highest node containing value 4 from its parent node (in the meanwhile we maintain the "min-pointer").

The only concern with this operation is the height of a heap. In the previous, the tree on the right hand side has height $3$ but contains only two keys. For a tree with $n$ keys, it could happens that it height is $\omega(\log n)$. Indeed, it could be as large as $O(n)$. This will invalidate the strategy we propose in the last section, which requires the height to be $O(\log n)$, to achieve the $O(\log n)$ amortized complexity for delete-min().

There are various ways to fix this, the idea of which will give rise to Pairing heap [Pairing heap achieve $O(\log n)$ amortized bound for deletion but requires $O(\log n)$ amortized time for both insertion and decrease-key(x). Its design philosophy is closely related to Splay tree.], Fibonacci heap, etc. Here we discuss about the solution of Quake heap.

First, Quake heap records the number of nodes at each height explicitly, denoted as $n_1, n_2, ..., n_H$, where $H$ is the maximum possible height. Further, it specifies a parameter $\alpha \in (0, 5, 1)$ and maintains the invariant that $n_{i + 1} \le \alpha \cdot n_i$ for each $i \ge 1$. This guarantees that $H = O(\log n)$.

In the following discussion, we take $\alpha = 0.75$.

Let's discuss how the maintain the invariant $n_{i + 1} \le \alpha n_i$ for all $i \ge 1$ for insert(x), decrease-key(x) and delete-min() operation.

1. For the operation insert(x), it create a singleton node at the bottom layer and increases $n_1$ by 1. If the invariant holds before insertion, it holds afterward.

   

   

2. For decrease, it will not change the number of nodes at each height. The following example shows the case where the children whose key is decreased is detached from its parent.

   

3. Delete-min is the most difficult part. To maintain the invariant, now delete-min() consists of four part:

   • Delete the min key (and all nodes that contain the min key). As before, this step may expose some children of the deleted nodes as new tree roots.
   • Recursively link all trees of the same height. After linking, scan all trees to maintain the min pointer.
   • Quake: if there is a level $i$ such that $n_{i + 1} > \alpha n_i$, remove all nodes with level greater than $i$.

It is left to analyze the running time step by step. We use a potential function for analysis. By previous section, the potential should contain the number of trees. Further, by the last step of delete-min operation, it is suggested to includes the number of nodes in the potential function, to cover the cost of node removal. Inspired by this, our first design is given by

We analyze the time for each step of delete-min()

1. Before delete-min(), the invariant holds and therefore the maximum height $H = O(\log n)$. Deleting the min-key and its associated nodes take actual time $O(\log n)$. As for $\Phi$, the number of nodes decreases (indeed, this decrease will cover the removal of the nodes containing the min key) and the number of trees increases by at most $O(\log n)$. Therefore, the amortized cost for the first step is $O(\log n)$.

2. Linking two trees of the same height has actual cost $1$. It creates a new node and decreases the number of trees by 1. Therefore, $\Delta \Phi = -1$. Hence the amortized cost is 0. This also explains why we need an coefficient 2 associated with #trees in the potential function. It is left to analyze the cost of scanning all tree. After linking, all trees are of different height. It suffices to show that the maximum height is $O(\log n)$ to bound the scanning cost to $O(\log n)$. Before linking $H = O(\log n)$. As there are only $n$ keys, there are at most $n$ trees with height $H$ before and during the linking procedure. Linking $n$ trees of the same height results in a new tree with height $\log n$. Therefore, after linking, $H$ increases by at most $\log n$ and $H = O(\log n)$ still holds. Therefore, the amortized cost for the second step is $O(\log n)$.

3. Suppose in this step we delete $k$ nodes. The actual cost is $k$. However, the number of nodes decreases by $k$. It seems that the amortized cost is 0 for this step. But it isn't. We have increased the number of tree. Denote $d_{i + 1}$ the number of nodes at level $i + 1$ with two children before removal and $s_{i + 1}$ the number of nodes with only one children. We have $n_{i + 1} = d_{i + 1} + s_{i + 1}$. On the other hand, we know $n_i \ge 2 d_{i + 1} + s_{i + 1}$. By the fact that $n_{i + 1} > \alpha n_i$, we know that

   $$\begin{aligned} s_{i + 1} &= 2(d_{i + 1} + s_{i + 1}) - (2 d_{i + 1} + s_{i + 1})\\ &\ge 2 n_{i + 1} - n_i \\ &\ge (2 \alpha - 1) n_i \end{aligned}$$

   as we create at most $n_i$ new trees, we can charge the creation of new trees into $s_{i + 1}$ and modify the potential as

   $$\Phi = \# \text{nodes} + 2 \cdot \# \text{trees} + \frac{2}{2\alpha - 1} \# \text{nodes with one child}$$

   Now step 3 has amortized cost 0. For other steps, this modification will increase the cost of decrease-key(x) by at most $O(1)$.

   

Caveat: we can't swap the order of step 2 and step 3, since linking tree may create violation to the invariant and we need step 3 to fix this.

Reference

[1] Chan, Timothy M. "Quake heaps: a simple alternative to Fibonacci heaps." In Space-Efficient Data Structures, Streams, and Algorithms, pp. 27-32. Springer, Berlin, Heidelberg, 2013.