Jump to content

Soft heap

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Fredrik (talk | contribs) at 11:37, 30 May 2004 (Category:data structures). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Soft_heap&oldid=6352673"