Soft Heap

Soft heap is an approximate mergeable priority queue data structure within computation and algorithms that breaks the Ω(log n) information-theoretic comparison barrier for priority queues by permitting controlled key corruption. Invented by French-American computer scientist Bernard Chazelle in 2000 (following a precursor structure introduced in 1998), a soft heap parameterized by an error rate 0 < ε ≤ 1/2 supports Insert, Find-Min, Meld, and Delete-Min in deterministic amortized time by allowing the internal keys of at most εN elements (after N total insertions) to be artificially increased—a process termed corruption.

In the algebraic comparison model, any strict priority queue such as a Fibonacci heap or pairing heap must spend Ω(log n) amortized comparisons per Delete-Min operation because n insertions followed by n minimum extractions sort n numbers in Ω(n log n) comparisons. By relaxing strict ordering so that a controlled fraction ε of items may have their priority keys raised (while never lowered), a soft heap executes Insert, Find-Min, and Meld in O(1) amortized time and Delete-Min in O(1) amortized uncorrupted work plus O(log(1/ε)) amortized time charged per corrupted insertion—equivalently O(log(1/ε)) amortized time for Insert and O(1) amortized time for every other operation. This trade-off forms the core engine of Chazelle's deterministic O(m α(m, n)) minimum spanning tree algorithm.

The Corruption Invariant and Entropy Saving

Let a soft heap process a sequence of operations that includes N total Insert(x, k) operations, where each item x arrives with an original key k(x). Internally, the soft heap associates each currently stored item x with a current key c(x) ≥ k(x), called its ckey. Whenever the structure raises c(x) above its original value k(x), item x is said to be corrupted. The soft heap enforces three guarantees at all times:

1. One-Sided Monotonicity (Raising Only): For every item x in the heap, its current key satisfies c(x) ≥ k(x). Keys are never artificially decreased.
2. Heap Order With Respect to Current Keys: Delete-Min and Find-Min return an item x whose current key c(x) is minimal among all items currently residing in the soft heap (which guarantees that k(x) ≤ c(x) ≤ c(y) for all remaining items y).
3. Bounded Corruption Budget: At any instant after N cumulative insertions (even if many items have already been deleted), at most εN items currently inside the soft heap are corrupted.

From an information-theoretic perspective, grouping items together under a shared upper-bound key c destroys ordering entropy among the grouped items. If the soft heap packs up to s items into a single node list sharing one common key c = max_i k(x_i), then s − 1 of those items become corrupted, but the data structure performs only 1 heap comparison per batch of s items rather than s separate heap comparisons. Setting the rank threshold r = ⌈log₂(1/ε)⌉ + 5 ensures that the fraction of corrupted items stays bounded below ε while reducing the comparison cost per element from O(log n) to O(r) = O(log(1/ε)).

Node Lists, Rank Threshold r, and Sifting

Structurally, a soft heap consists of a forest of heap-ordered binomial-like trees ordered by increasing rank k, linked at their roots via a doubly linked list supplemented by suffix-minimum pointers (so Find-Min takes O(1) worst-case time). Unlike a standard binomial heap or Fibonacci heap in which each tree node holds exactly one item, each node v of rank k in a soft heap holds a linked item list list(v) containing one or more items, all assigned the same common key c(v) equal to the maximum original key among items ever placed into list(v).

Chazelle calls this mechanism carpooling: multiple items share a single node v and travel through the heap together using only one key comparison per node move, at the cost of raising every passenger's effective key to the highest key in the carpool c(v).

The target capacity of list(v) depends on the node's rank k relative to the error threshold parameter r = ⌈log₂(1/ε)⌉ + 5:

• Uncorrupted Lower Levels (Rank k ≤ r): For every node v of rank k ≤ r, the target list size is 1. No carpooling or corruption occurs at ranks 0 through r, so every item at depth ≤ r retains its true uncorrupted key c(x) = k(x).
• Corrupted Upper Levels (Rank k > r): Above rank r, the target list size grows exponentially with rank. In Chazelle's formulation (and the simplified Kaplan–Zwick variant, 2009), a node of rank k > r maintains an item list whose size grows by a constant factor (such as 3/2 per rank increment, or 2^{⌈(k−r)/2⌉}), updated via a recursive procedure called Sift(v).

The Sift Procedure and Double-Pull Refilling

When Delete-Min removes an item from the root's item list list(root), two cases arise:

1. If list(root) still contains remaining items, Delete-Min simply extracts the next item from list(root) in O(1) time without performing any key comparisons or tree restructuring.
2. If list(root) becomes empty (or falls below half its rank capacity), the root calls Sift(v) to replenish its item list from its children.

In Sift(v), node v identifies its child u with the smallest current key c(u), concatenates list(u) onto list(v), updates c(v) ← max(c(v), c(u)), and recursively replenishes u. If node v has rank k > r (or an even rank above r in the Kaplan–Zwick construction) and its replenished list is still below capacity, Sift(v) performs a second pull from the new minimum-key child of v, concatenating two child lists into list(v) and raising all items in the first pull to the higher key c(u₂) of the second pull. This double pull doubles the carpool size every two levels above rank r, guaranteeing both that Sift calls decay geometrically above rank r (yielding O(r) = O(log(1/ε)) amortized work per insertion) and that the total number of corrupted items in all nodes of rank k > r sums a geometric series bounded by:

(Note: By shifting the potential function, a soft heap can equivalently be analyzed as taking O(1) amortized time for Insert, Find-Min, Meld, and uncorrupted Delete-Min, plus O(log(1/ε)) amortized time per item that becomes corrupted.)

Chazelle's Deterministic O(m α(m, n)) Minimum Spanning Tree Algorithm

Before the invention of the soft heap, the fastest deterministic comparison-based minimum spanning tree algorithm was Bernard Chazelle's 1997 O(m α(m, n) log α(m, n)) method, whereas Karger, Klein, and Tarjan (1995) had achieved linear O(m) expected time using randomization. In 2000, Chazelle used soft heaps to achieve deterministic O(m α(m, n)) time, where α is the inverse Ackermann function, and Seth Pettie and Vijaya Ramachandran (2002) subsequently used soft heaps to construct a provably optimal deterministic comparison-based minimum spanning tree algorithm.

How can an approximate priority queue that corrupts edge weights produce the true minimum spanning tree? Chazelle's insight relies on the cycle and cut properties of graphs:

1. Raising the weight of an edge e to c(e) > w(e) makes e appear heavier than it truly is, which only delays its selection during Borůvka-like vertex contractions.
2. When a soft heap returns a minimum-ckey incident edge e leaving an active component, c(e) is guaranteed to be ≤ c(f) for all other incident edges f, though some corrupted edge f might have a smaller true weight w(f) < w(e).
3. After a bounded phase of component contractions using soft heaps with error rate ε, at most εm edges have been corrupted. The algorithm simply identifies all corrupted edges, restores their original weights w(f), and recursively filters them! Because only an ε fraction of edges are corrupted, the recursive cleanup work is bounded by O(εm) while each soft-heap operation costs only O(log(1/ε)), breaking the logarithmic priority-queue bottleneck.

Deterministic Linear-Time Selection and Exact Medians

As a direct demonstration of soft heaps, consider finding the median (or k-th smallest element) of n unsorted elements in deterministic O(n) time (replacing the Blum–Floyd–Pratt–Rivest–Tarjan median-of-medians pivot algorithm):

1. Insert all n elements into a soft heap with error parameter ε = 1/3 in O(n log(1/ε)) = O(n) total time.
2. Execute n/3 Delete-Min operations in O(n) time, and let p be the maximum original key k(x) among all n/3 extracted elements.
3. Because every extracted element had k(x) ≤ p, at least n/3 elements in the input are ≤ p. Conversely, for every element y still remaining in the soft heap, its current key satisfies c(y) ≥ c(last extracted) ≥ k(last extracted). At most εn = n/3 of those remaining elements are corrupted; all remaining uncorrupted elements (at least n − n/3 − n/3 = n/3 elements) satisfy k(y) = c(y) ≥ p!
4. Thus p is guaranteed to be a balanced pivot with at least n/3 elements ≤ p and at least n/3 elements ≥ p, yielding deterministic linear-time selection via T(n) ≤ T(2n/3) + O(n) = O(n).

Why can a soft heap only raise keys and never lower them?

If a priority queue were allowed to artificially lower keys, a single outlier element with a huge true key could have its key lowered to −∞ and be returned on the very first Delete-Min, providing zero information about the true minimum of the remaining elements. Because a soft heap only raises keys (c(x) ≥ k(x)), whenever Delete-Min returns an element x with current key c(x), that value c(x) is a valid lower bound on the current key of every remaining element in the heap, and therefore a valid lower bound on the true key of every remaining uncorrupted element (at least n − εN elements).

Does the corruption bound εN depend on the current heap size n or total insertions N?

The corruption bound is at most εN, where N is the total number of insertions performed since the soft heap was created (or across all soft heaps melded into it), rather than the current number of surviving elements n. If many deletions reduce n below 2εN, a high proportion of the remaining elements could be corrupted. To maintain a bound proportional to the current size n, algorithms periodically rebuild the soft heap from scratch every Ω(εN) deletions, which adds only O(log(1/ε)) amortized cost per deletion.

What is the Kaplan–Zwick simplified soft heap?

In 2009, Haim Kaplan and Uri Zwick showed that Chazelle's binomial tree structure can be replaced by complete binary heap-ordered trees whose root ranks match standard binomial-heap binary carry addition, and where double-pull sifting occurs at every even rank above the threshold r = ⌈log₂(1/ε)⌉ + 5. Their construction achieves the same O(log(1/ε)) overhead and εN corruption bound with a shorter amortized potential analysis.

1. Chazelle, B. (2000). "The soft heap: An approximate priority queue with optimal error rate." Journal of the ACM, 47(6), 1012–1027. https://doi.org/10.1145/355541.355554
2. Chazelle, B. (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity." Journal of the ACM, 47(6), 1028–1047. https://doi.org/10.1145/355541.355562
3. Pettie, S., & Ramachandran, V. (2002). "An optimal minimum spanning tree algorithm." Journal of the ACM, 49(1), 16–34. https://doi.org/10.1145/505241.505243
4. Kaplan, H., & Zwick, U. (2009). "A simpler implementation and analysis of Chazelle's soft heaps." In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), 477–485. https://doi.org/10.1137/1.9781611973068.53