Soft heap

Definition and performance

The constant time operations are:

• create(S): Create a new soft heap
• insert(S, x): Insert an element into a soft heap
• meld(S, S'): Combine the contents of two soft heaps into one, destroying both
• delete(S, x): Delete an element from a soft heap
• findmin(S): Get the element with minimum key in the soft heap

Other heaps such as Fibonacci heaps achieve most of these bounds without any corruption, but cannot provide a constant-time bound on the critical delete operation. The amount of corruption can be controlled by the choice of a parameter ${\displaystyle \epsilon }$, but the lower this is set, the more time insertions require: expressed using Big-O notation, the amortized time will be ${\displaystyle O(\log 1/\epsilon )}$ for an error rate of ${\displaystyle \epsilon }$. Some versions of soft heaps allow the create, insert, and meld operations to take constant time in the worst case, producing amortized rather than worst-case performance only for findmin and delete. As with comparison sort, these algorithms access the keys only by comparisons; if arithmetic operations on integer keys are allowed, the time dependence on ${\displaystyle \epsilon }$ can be reduced to ${\displaystyle O(\log \log 1/\epsilon )}$ or (with randomization) $O(\sqrt{\log \log 1/\epsilon })$.

More precisely, the error guarantee offered by the soft heap is the following: each soft heap is initialized with a parameter ${\displaystyle \epsilon }$, chosen between 0 and 1/2. Then at any point in time it will contain at most ${\displaystyle \epsilon \cdot n}$ corrupted keys, where ${\displaystyle n}$ is the number of elements inserted so far. Note that this does not guarantee that only a fixed percentage of the keys currently in the heap are corrupted: in an unlucky sequence of insertions and deletions, it can happen that all elements in the heap will have corrupted keys. Similarly, there is no guarantee that in a sequence of elements extracted from the heap with findmin and delete, only a fixed percentage will have corrupted keys: in an unlucky scenario only corrupted elements are extracted from the heap. When a key is corrupted, the value stored for it in the soft key is higher than its initially-given value; corruption can never decrease the value of any key. The findmin operation finds the minimum value among the currently stored keys, including the corrupted ones.

The soft heap was designed by Bernard Chazelle in 2000. The term "corruption" in the structure is the result of what Chazelle called "carpooling" in a soft heap. Each node in the soft heap contains a linked list of keys and one common key. The common key is an upper bound on the values of the keys in the linked list. Once a key is added to the linked list, it is considered corrupted because its value is never again relevant in any of the soft heap operations: only the common keys are compared. This is what makes soft heaps "soft"; one cannot be sure whether any particular value put into it will be corrupted. The purpose of these corruptions is effectively to lower the information entropy of the data, enabling the data structure to break through information-theoretic barriers regarding heaps.