The Soft heap reference article from the English Wikipedia on 24-Jul-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Soft heap

In computer science, the soft heap is a data structure and a variant on the simple heap designed by Bernard Chazelle in 2000. By carefully "corrupting" a certain small percentage of values in the heap, it is able to achieve amortized constant-time bounds for all operations. A bound can be set on the percentage of values which are corrupted, but the lower this is set, the more time insertions require.

External link

• Chazelle's original paper (ps) (pdf) directly from the author's website, including C code.

This article is a stub. You can help Wikipedia by expanding it.

This is the "Soft heap" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.