Quake Heap

Quake Heap is a mergeable comparison-based priority queue data structure in computation and algorithms invented by Timothy M. Chan (circulated as a 2009 manuscript and published in Space-Efficient Data Structures, Streams, and Algorithms in 2013) that matches the optimal asymptotic time bounds of a Fibonacci heap—O(1) worst-case time for Insert, Find-Min, Meld, and Decrease-Key, and O(log n) amortized time for Delete-Min—without maintaining node mark bits, performing cascading cuts, or updating ancestor ranks during Decrease-Key. Instead of storing one node per element and readjusting local rank invariants along an ancestor path when a key decreases, a quake heap represents a priority queue as a forest of binary tournament trees in which each element x occupies a vertical path of cloned nodes from a leaf at level 0 up to its current tournament peak at height h(x).

Because Decrease-Key(x, k) simply severs the single pointer directly above the highest tournament node of x and updates the key of x in O(1) worst-case time without inspecting or modifying any ancestor nodes, repeated cuts can gradually thin out the lower levels of the tournament forest. To prevent tree heights from exceeding O(log n), Delete-Min checks a global exponential level-size decay condition n_i+1 ≤ α n_i (for a fixed constant α ∈ (1/2, 1), such as α = 3/4) and triggers a top-down "quake" (earthquake) reconstruction that demolishes all tournament nodes above the lowest violating level i₀ whenever upper levels become too sparse relative to their height.

In classical priority queues designed for Dijkstra's algorithm and Prim's algorithm for minimum spanning trees, achieving O(1) amortized Decrease-Key alongside O(log n) Delete-Min requires bounding the maximum degree or height of every root tree by O(log n) even after an adversary cuts arbitrary subtrees from the interior of the trees:

• In a Fibonacci heap, each node stores a Boolean mark bit recording whether it has already lost one child; losing a second child triggers a recursive cascading cut up the parent spine.
• In a rank-pairing heap, only one cut occurs per Decrease-Key, but an upward pass must still walk parent pointers to decrement integer node ranks and maintain Type-1 or Type-2 rank-difference rules.
• In a hollow heap, Decrease-Key avoids cutting edges by leaving a hollow node in place and introducing a second-parent pointer that turns the tree into a directed acyclic graph (DAG).

Timothy M. Chan observed that all local per-node bookkeeping during Decrease-Key can be eliminated if the invariant guaranteeing logarithmic tree height is enforced globally across entire height levels during Delete-Min, in direct analogy to scapegoat trees and global rebuilding techniques for deletion in static data structures.

A quake heap stores a dynamic set of n elements inside a forest of rooted binary trees satisfying the structure of a knockout tournament:

1. Leaves and Active Elements: Each stored element x is associated with a unique leaf node at level 0 (height 0).
2. Vertical Path of Cloned Nodes: Whenever two roots u and v at height i are linked during a tournament match, a new parent node w is allocated at height i + 1 with left child u and right child v, and w is labeled as a clone of whichever child holds the smaller key (say, x). Consequently, every element x in the priority queue corresponds to a contiguous vertical chain of nodes from level 0 (its leaf) up to some peak level h(x) ≥ 0, where every node on the chain of x references the same underlying element x and shares its current key key(x).
3. One-Child and Two-Child Internal Nodes: Initially, when a tournament node w is created at height i + 1 by linking two roots at height i, w has two children of height i—one belonging to the vertical chain of the winning element x, and the other serving as the peak of the losing element y. If a subsequent Decrease-Key or Delete-Min severs the losing child y, w remains at height i + 1 with only one child (the node of x at height i). Thus, every node at level i > 0 has either one or two children at level i − 1, and at least one of those children always represents the same element x as its parent.

Node Level Counts and Height Stratification

Unlike a pairing heap or splay tree where node depths fluctuate implicitly when subtrees are moved, the height (level) i of a tournament node in a quake heap is fixed at creation time and never changes for the lifetime of that node:

• A leaf node always remains at level 0.
• A node created by linking two level-i roots always remains at level i + 1 until it is destroyed during Delete-Min or demolished during a quake.
• The data structure maintains a global array of integer counters n₀, n₁, n₂, ..., n_H, where n_i denotes the total number of tournament nodes currently existing at level i across all trees in the forest (n₀ = n).

Memory and Pointer Representation

Each tournament node u at level i stores a pointer to its underlying element item(u) = x, pointers to its left and right children at level i − 1, and a parent pointer parent(u) at level i + 1, while the element record x stores key(x) and a pointer top(x) to the highest tournament node on x's vertical path (at level h(x)). Alternatively, in the compressed representation, each element x stores a linked list of the losing sibling roots defeated by x at levels 0, 1, ..., h(x) − 1.

Find-Min, Insert, and Meld in O(1) Worst-Case Time

The quake heap maintains its tournament roots in a root list together with a pointer minRoot to the root holding the minimum key:

• Find-Min(Q): Returns the element associated with minRoot in O(1) worst-case time.
• Insert(x, k, Q): Allocates a leaf node for x at level 0 with key(x) = k and top(x) pointing to that leaf, increments n₀ ← n₀ + 1, inserts the leaf into the root list, and updates minRoot if k < key(minRoot) in O(1) worst-case time.
• Meld(Q₁, Q₂): Concatenates the root lists of Q₁ and Q₂ and updates minRoot to the smaller of the two minimum roots in O(1) worst-case time.

Decrease-Key in O(1) Worst-Case Time via Single-Edge Severing

Suppose Decrease-Key(x, k, Q) decreases the key of element x to k < key(x). Let u = top(x) be the highest node on the vertical clone path of x (at level h(x)):

1. Key Update: Set key(x) = k. Because every node on the vertical chain of x from level 0 to level h(x) references key(x) (and already defeated its sibling subtree at every level ≤ h(x)), lowering key(x) preserves the tournament ordering at every node on x's vertical path below u.
2. Root Check: If u is already a root (parent(u) = null), update minRoot if k < key(minRoot).
3. Single-Pointer Cut Above top(x): If u is not a root, let w = parent(u) be the tournament node at level h(x) + 1 where x previously lost a tournament match. Detach u from w by clearing the child pointer of w that pointed to u and setting parent(u) = null. Insert u as a new tournament tree root at level h(x) in the root list, and update minRoot if k < key(minRoot).

No ancestor of w, no level counter n_i, and no sibling subtree is touched, so Decrease-Key executes in O(1) worst-case time.

Delete-Min, Pairwise Root Linking, and the Global Quake Operation

When Delete-Min(Q) is called on a non-empty quake heap, let x be the minimum element located at minRoot:

1. Vertical Path Removal: Delete the vertical chain of tournament nodes belonging to x from level h(x) down to its leaf at level 0. For each level i ∈ {0, 1, ..., h(x)}, decrement n_i ← n_i − 1, destroy the level-i node of x, and if that node had a surviving sibling child v at level i − 1, promote v into the root list as a root at level i − 1.
2. Tournament Consolidation (Pairwise Linking by Level): Group all current tournament roots by their fixed level i ∈ {0, 1, ..., H}. Iterating from i = 0 upward: while at least two roots u and v exist at level i, remove u and v from the root list, compare their keys, allocate a new parent tournament node w at level i + 1 as a clone of the winner with children u and v, increment n_i+1 ← n_i+1 + 1, and place w into the bucket of roots at level i + 1.
3. Global Quake Check (Exponential Decay Enforcement): For a fixed decay constant α ∈ (1/2, 1), typically α = 3/4, scan the level counters n₀, n₁, ..., n_H from i = 0 upward to test the height-decay invariant:

n_i+1 ≤ α · n_i When every level i satisfies n_i+1 ≤ α n_i, the maximum non-empty level H satisfies n · α^H ≥ 1, so H ≤ log_1/α n = O(log n). If some level violates the condition, let i₀ be the smallest index such that n_i0+1 > α n_i0, and trigger a quake at level i₀: destroy all tournament nodes at every level i > i₀ (resetting n_i = 0 for all i > i₀) so that every node at level i₀ whose parent was destroyed becomes a tournament root at level i₀.

A fresh tournament link at level i creates one parent node at level i + 1 from two children at level i, establishing a 1-to-2 ratio (n_i+1 ≤ 0.5 n_i). For the ratio n_i+1 / n_i to deteriorate from ≤ 0.5 to > α (such as > 0.75), at least (2 − 1/α) n_i+1 degree-1 nodes must have been created at level i₀ + 1 by Decrease-Key cuts or Delete-Min deletions since level i₀ was last rebuilt.

Define the potential function Φ = c₁ · R + c₂ · D₁, where R is the total number of tournament roots and D₁ is the total number of degree-1 internal nodes across all levels:

• Insert increases R by 1 (O(1) amortized cost), and Decrease-Key increases R by at most 1 and D₁ by at most 1 (O(1) amortized cost).
• During Delete-Min, removing the minimum element's vertical path of height H ≤ log_1/α n adds at most H roots (O(log n) potential increase), pairwise linking pays for itself via the drop in R, and when a quake occurs at the lowest violating level i₀, the total number of demolished nodes above i₀ is bounded by the geometric series ∑_{i > i0} n_i ≤ n_i0+1 / (1 − α), which is paid for by eliminating the > (2 − 1/α) n_i0+1 degree-1 nodes at level i₀ + 1 from D₁.
• Furthermore, because n₀ = n and n_i+1 ≤ α n_i after every Delete-Min, total space is bounded by ∑ n_i ≤ n / (1 − α) = O(n) (at most 4n nodes for α = 3/4).

Why is it called a quake heap?

Timothy M. Chan named the structure a quake heap because its periodic rebuilding step during Delete-Min acts like a structural "earthquake": whenever cuts from Decrease-Key have eroded the lower levels of the tournament forest so that some upper level i₀ + 1 contains more than a fraction α of the nodes in level i₀ (n_i+1 > α n_i), all tournament nodes above level i₀ are demolished at once, reducing the surviving trees back to height i₀.

How does Decrease-Key in a quake heap avoid touching ancestors?

In a quake heap, each element x is represented by a vertical chain of cloned tournament nodes from level 0 up to level h(x). Lowering the key of x makes x even more competitive in every tournament match it already won at levels ≤ h(x). The only match where x's new key could change the outcome is the match x lost at level h(x) + 1; severing the single pointer between top(x) and its parent at level h(x) + 1 detaches x's tournament subtree in O(1) worst-case time without visiting any higher ancestors.

What is the best choice for the decay parameter α in a quake heap?

The decay parameter α must satisfy 1/2 < α < 1. If α were ≤ 1/2, even a freshly linked complete binary tournament tree (where n_i+1 = n_i / 2) would trigger a quake; if α were ≥ 1, tree heights would not be bounded by O(log n). Choosing α = 3/4 balances the maximum tree height log_4/3 n ≈ 2.41 log₂ n against the frequency of quakes, ensuring that a quake at level i₀ only occurs after at least half of the nodes at level i₀ + 1 have lost a child.

1. Chan, T. M. (2013). "Quake Heaps: A Simple Alternative to Fibonacci Heaps." In A. Brodnik, A. López-Ortiz, V. Raman, & A. Viola (Eds.), Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, Lecture Notes in Computer Science, vol. 8066, pp. 27–32. Springer. https://doi.org/10.1007/978-3-642-40273-9
2. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
3. Haeupler, B., Sen, S., & Tarjan, R. E. (2011). "Rank-Pairing Heaps." SIAM Journal on Computing, 40(6), 1463–1485. https://doi.org/10.1137/100785351
4. Hansen, T. D., Kaplan, H., Tarjan, R. E., & Zwick, U. (2017). "Hollow Heaps." ACM Transactions on Algorithms, 13(3), Article 42, 1–27. https://doi.org/10.1145/3093240
5. Elmasry, A. (2010). "The Violation Heap: A Relaxed Fibonacci-Like Heap." Discrete Mathematics, Algorithms and Applications, 2(4), 493–503. https://doi.org/10.1142/S1793830910000838