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:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 ε).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Soft heap: Applications ►



 

Computer science: Computer science (abbreviated CS or compsci) encompasses a variety of topics that relates to computation, like abstract analysis of algorithms, formal grammars, and subjects such as programming languages, program design, software, computer hardware, artificial intelligence, and numerical analysis. B...

Heap: :This page discusses the heap data structure. For the place from which memory is dynamically allocated, see heap (programming)....

Data structure: In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow a more efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data structure. A we...




Soft heap related Images and Photos (experimental)

Soft Skin	Soft Shells	Soft Winter	Soft Elements
Soft Breeze I	Todd Heap	Soft Kitty Shirt	Soft Green Grove
Soft Kitty Babydoll	Teddybears: Soft Machine CD	Teddybears: Soft Machine CD	Soft And Dreamy