User:Connordhenderson/sandbox

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

A Quake heap is a data structure that implements the basic priority queue operations: insert, delete-min, union, and decrease-key. Quake heaps are a list of trees that store its elements within their leaves. The internal nodes of a Quake heap have a value equal to the smallest value amongst its children; this child node also stores a pointer to the highest instance of that value in the tree. Quake heaps must satisfy the following properties:

• The data structure follows the heap-ordering property
• All paths from a node x to a leaf node are the same length; this length is called the height of x
• Internal nodes have a degree of 1 or 2

The data structure has similar amortized 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 .

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 for the consolidate step like a Fibonacci heap would, the consolidate analogue of a Quake heap stores the trees in an array indexed by heights and links them in the same fashion when a restructuring occurs due to a violation of an invariant described below.

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 element within its tree. A Quake heap may have numerous trees contained within it, however, so the root of a tree is not necessarily the smallest element within the entire heap.

Quake heaps perform lazy updates which often lead to the data structure being in an unideal state if it has not undergone restructuring for some time. To avoid imbalance, an invariant is maintained during the delete-min() operation:

• Let n_i be the number of nodes at height i
• For some constant $\alpha \in ({\frac {1}{2}},1),\forall _{i}n_{i+1}\leq \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 height 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 could 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 the highest occurrence of the value x is cut, causing a new tree to be created, and the value of the node from the cut node's pointer is updated to k. Lots of Decrease-Key operations may result in a tree with many tall 1-child only branches; an invariant is introduced to maintain the data-structure during delete-min() to restructure the Quake heap when the number of these branches exceeds a given threshold, as outlined in the section 'Structure'.

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

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

• Cut the path containing the minimum element
• Merge trees of the same height, similar to Fibonacci Heap
• If necessary, restore invariant by removing 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 amortized time per operation can be analyzed using the potential method. The state of the data structure can largely be represented by three quantities, the number of nodes (since a larger number of nodes means a 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: $\Phi =N+T+{\frac {1}{2\alpha -1}}B$

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

Insert(x):

Pseudocode:

1. create a new tree containing ''x''

Impact on potential function:

$\Delta T=1$

$\Delta N=1$

Actual cost is $O(1)$

$\Phi =\Phi +2,\quad \Delta \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:

$\Delta T=1$

$\Delta B=1$

Actual cost is $O(1)$

$\Phi =\Phi +1+{\frac {1}{2\alpha -1}}B=\Phi +3,\quad \Delta \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); $\quad \therefore$ Actual cost = T + O(log n)

$\Delta T=O(logn)-T,\Delta B\leq 0;\quad \therefore \Delta \Phi \in O(logn)$

$\Delta N<0,\Delta T\leq n_{i},b_{i+1}\geq 2n_{i+1}-n_{i}>{\frac {1}{2}}n_{i}$

$\Delta B\leq b_{i}<{\frac {1}{2}}n_{i}$

$\therefore \Delta \Phi =\Delta N+\Delta T+2\Delta B\leq 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:

$\Delta N=1$

$\Delta T=-1$

Actual cost is $O(1)$

$\Phi =\Phi +1-1=\Phi ,\quad \Delta \Phi =0$

Amortization of Quake Heap Operations

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

The negative $\Phi$ for delete-min() implies that the decrease of the potential of the data structure is paying the difference; its 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

Category:Heaps (data structures) Category:Amortized data structures