Soft heap

In computer science, the soft heap is a variant on the simple heap data structure designed by Bernard Chazelle in 2000. By carefully "corrupting" (increasing) the keys of at most a certain fixed percentage of values in the heap, it is able to achieve amortized constant-time bounds for all five of its operations:

Related Topics:
Computer science - Heap - Data structure - Bernard Chazelle - Amortized

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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

The term "corruption" here indicates that a corrupted key's value has been changed by the data structure from the correct value which was initially inserted to a larger, incorrect value. It is unpredictable which keys will be corrupted in this manner; it is only known that at most a fixed percentage will be changed. This is what makes soft heaps "soft"; you can't be sure whether or not any particular value you put into it will be modified. 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.

Related Topics:
Information entropy - Information-theoretic

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 percentage of values which are corrupted can be chosen freely, but the lower this is set, the more time insertions require (O(log 1/ε) for an error rate of ε).

Related Topics:
Fibonacci heap - O

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

 
Soft heap: Applications ►