Quake Heap

Quake Heap
Type	heap
Invented	2013
Invented by	Timothy M. Chan
Time complexity in big O notation
Algorithm Average Worst case Insert Θ(1) Find-min Θ(1)   Delete-min O(log n)   Decrease-key Θ(1)   Merge Θ(1)

A Quake heap is a data structure that implements the basic priority queue operations: insert, delete-min, union, and decrease-key. A Quake heap must satisfy the following properties:

• The data structure follows the heap-ordering properties
• Each internal node has a pointer to the smallest node amongst its children
• All paths from a node x to a leaf node are the same length; this length is denoted as the height at x
• Internal nodes have a degree of 1 or 2

The data structure has similaramortized running times for each of the supported operations as a Fibonacci heap but Fibonacci heaps require more nuanced understanding of the intermediate structures that form and inductive proofs in order to perform the analysis. Quake heaps, by contrast, avoid using techniques like marking nodes to be cut and as a result are much more straightforward to anaylze, assuming only a basic familiarity with amortized analysis. As such, quake heaps are well suited for educational environments to help students understand the process behind analyzing runtime complexities and are much simpler to implement.

Much like a Fibonacci heap, a quake heap relies on storing the individual trees within the heap in a list and performs the same linking process during the delete-min() operation. Instead of storing them by their degree, however, they store them by their heights and link them in the same fashion.

Structure

While quake heaps are less flexible in the shapes that are allowed due to the properties of the data structure, they are much simpler than a Fibonacci heap. Similarly, quake heaps are collections of rooted subtrees. They differ in that a quake heap resembles a tournament bracket where the smallest element is the winner and elements may receive a bye throughout the tournament in order to advance in the tree. In essence the winner of the tournament is the smallest number within its tree. A quake heap may have numerous trees contained within it, however, so the root of a tree is not the smallest element within the heap itself.

Quake heaps perform lazy updates which often lead to unideal To avoid imbalance, an invariant is followed:

• Let n_i be the number of nodes at height i
• For some constant $\alpha \in (\frac{1}{2},1),{\mathrm{\forall }}_i{n}_{i+1}\le \alpha n_i$

Implementation of operations

In order to insert an element x into the heap, we simply create a new node and insert it into a new tree. This results in a new tree of degree 0 composed solely of a node with value x.

To support decrease-key acting on element x and decreasing its priority to a value of k there are some significant departures from a Fibonacci heap. While the internal nodes are pointers to the smallest child node, and could thus be changed in one step, simply decreasing the key would cause a costly chains of updates since each level of the tree would need to be recalculated to ensure that the second property of quake heaps is upheld. Instead, the subtree at x is cut, causing a new tree is created, and the cut nodes pointer has its value updated to k. Lots of Decrease-Key operations may result in a tree with many tall branches; an invariant is introduced to maintain the data-structure during delete-min()

If we invalidate the invariant during delete-min(), we delete all nodes above the lowest i violation in all trees. This imposes a constraint on the height of the tree such that the maximum height is $lo{g}_{\frac{1}{\alpha }}n$

The steps for delete-min() are as follows:

• Cut the path containing the minimum element
• Merge trees of the same size, similar to Fibonacci Heap
• Resolve invariant by removing necessary nodes

To perform a union or meld between two trees:

• Clone the smallest root of between the two trees, x and y
• Set the roots of x and y to be the children of the cloned node

Cost Analysis

Defining the Potential Function

The state of our data structure can largely be represented by three quantities, the number of nodes (since larger nodes means larger graphs to traverse in order to get to the roots), the number of trees (in order to iterate to get the minimum value, or to link during delete-min), and the number of degree-1 nodes (since they are artifacts from operations that only seek to increase the runtime of root-finding components of the data structure).

Let N be the number of nodes

Let T be the number of trees

Let B be the number of degree-1 nodes

The potential function can be described as thus: $\mathrm{\Phi }=N+T+\frac{1}{2\alpha -1}B$

For simplicity, $\alpha =\frac{3}{4}$, thus $\mathrm{\Phi }=N+T+2B$

Insert(x)

Psuedocode:

1. create a new tree containing x

Impact on potential function:

$T=T+1$

$N=N+1$

Actual cost is $O(1)$

$\mathrm{\Phi }=\mathrm{\Phi }+2,\mathrm{\Delta }\mathrm{\Phi }\in O(1)$

---

Decrease-Key(x, k)

Pseudocode:

1. cut the subtree rooted at the highest node storing x

2. change x’s value to k

Impact on potential function:

$T=T+1$

$B=B+1$

Actual cost is $O(1)$

$\mathrm{\Phi }=\mathrm{\Phi }+1+\frac{1}{2\alpha -1}B=\mathrm{\Phi }+3,\mathrm{\Delta }\mathrm{\Phi }\in O(1)$

---

Delete-Min()

Pseudocode:

1. x ← minimum of all the roots

2. remove the path of nodes storing x

3. while there are 2 trees of the same height:

4. link the 2 trees

5. if ni+1 > ni for some i then:

6. let i be the smallest such index

7. remove all nodes at heights > i

8. return x

Impact on potential function:

Maximum height, O(log n); $\therefore$ Actual cost = T + O(log n)

$\mathrm{\Delta }T=O(logn)-T,\mathrm{\Delta }B\le 0;\therefore \mathrm{\Delta }\mathrm{\Phi }\in O(logn)$

$\mathrm{\Delta }N<0,\mathrm{\Delta }T\le n_i,b_{i+1}\ge 2n_{i+1}-n_i>\frac{1}{2}{n}_i$

$\mathrm{\Delta }B\le b_i<\frac{1}{2}{n}_i$

$\therefore \mathrm{\Delta }\mathrm{\Phi }=\mathrm{\Delta }N+\mathrm{\Delta }T+2\mathrm{\Delta }B\le 0$

---

Union(x, y)

Pseudocode:

1. clone the node with the smaller value between x and y’s roots

2. set x and y’s roots to point to the clone

Impact on potential function:

$N=N+1$

$T=T-1$

Actual cost is $O(1)$

$\mathrm{\Phi }=\mathrm{\Phi }+1-1=\mathrm{\Phi },\mathrm{\Delta }\mathrm{\Phi }=0$

Amortization of Quake Heap Operations

Operation	Actual Cost	$\mathrm{\Delta }\mathrm{\Phi }$	Amortized Cost
insert(x)	O(1)	2	O(1) > 0
decrease-key(x, k)	O(1)	3	O(1) > 0
delete-min()	O(log n)	< 0	O(log n)
union(x, y)	O(1)	0	O(1) > 0

The negative $\mathrm{\Phi }$ for delete-min() implies that the decrease of the potential of the data structure is paying the difference; it's actual cost is still bounded by O(log n). Since the amortized costs are constant values and we assume we start with an empty structure, the complexity of Quake Heaps falls under the O(log n) category.

Summary of Heap Running Times

Here are time complexities of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operation	find-min	delete-min	insert	decrease-key	meld
Binary	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial	Θ(1)	Θ(log n)	Θ(1)	Θ(log n)	O(log n)
Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Pairing	Θ(1)	O(log n)	Θ(1)	o(log n)	Θ(1)
Brodal	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Strict Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap	O(log n)	O(log n)	O(log n)	Θ(1)	?
Quake Heap	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)

References

This article "Quake Heap" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Quake Heap. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---