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:
Comments
By far the coolest data structure is the soft heap (http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-he...).
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:
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.