Re:What are the lesser known but cool data structures?
by igravious on Sunday May 23, 2010 @11:49AM
(#1372454)
Off-topic but meh. The guy is a frighteningly funny and shrewd to boot. See any of his posts at A Tiny Revolution http://www.tinyrevolution.com/mt/
Oh a thanks for the heads-up on this data structure ljlolel.
From wikipedia: http://en.wikipedia.org/wiki/Soft_heap
In computer science, the soft heap, designed by Bernard Chazelle in 2000, is a variant on the simple heap data structure. 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: