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:
The term "corruption" here is the result of what Chazelle called "carpooling" in a soft heap. Each node in the soft heap contains a li...
more
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:
The term "corruption" here is the result of what Chazelle called "carpooling" in a soft heap. Each node in the soft heap contains a linked-list of keys and one common key. The common key is an upper bound on the values of the keys in the linked-list. Once a key is added to the linked-list, it is considered corrupted because its value is never again relevant in any of the soft heap operations: only the common keys are compared. It is unpredictable which keys will be corrupted in this manner; it is only known that at most a fixed percentage will be corrupted. This is what makes soft heaps "soft"; you can't be sure whether or not any particular value you put into it will be...
less
