Soft heap
Variant on the simple heap data structure / From Wikipedia, the free encyclopedia
For the band, see Soft Heap.
In computer science, a soft heap is a variant on the simple heap data structure that has constant amortized time complexity for 5 types of operations. This is achieved by carefully "corrupting" (increasing) the keys of at most a constant number of values in the heap.