Applications
Surprisingly, soft heaps are useful in the design of deterministic algorithms, despite their unpredictable nature. They were used to achieve the best complexity to date for finding a minimum spanning tree. They can also be used to easily build an optimal selection algorithm, as well as near-sorting algorithms, which are algorithms that place every element near its final position, a situation in which insertion sort is fast.
One of the simplest examples is the selection algorithm. Say we want to find the kth largest of a group of n numbers. First, we choose an error rate of 1/3; that is, at most 33% of the keys we insert will be corrupted. Now, we insert all n elements into the heap — at this point, at most n/3 keys are corrupted. Next, we delete the minimum element from the heap about n/3 times. Because this is decreasing the size of the heap, it cannot increase the number of corrupted elements. Thus there are still at most n/3 keys that are corrupted.
Now at least 2n/3 − n/3 = n/3 of the remaining keys are not corrupted, so each must be larger than every element we removed. Let L be the element that we have removed with the largest (actual) value, which is not necessarily the last element that we removed (because the last element we removed could have had its key corrupted, or increased, to a value larger than another element that we have already removed). L is larger than all the other n/3 elements that we removed and smaller than the remaining n/3 uncorrupted elements in the soft heap. Therefore, L divides the elements somewhere between 33%/66% and 66%/33%. We then partition the set about L using the partition algorithm from quicksort and apply the same algorithm again to either the set of numbers less than L or the set of numbers greater than L, neither of which can exceed 2n/3 elements. Since each insertion and deletion requires O(1) amortized time, the total deterministic time is T(n) = T(2n/3) + O(n). Using case 3 of the master theorem (with ε=1 and c=2/3), we know that T(n) = Θ(n).
The final algorithm looks like this:
function softHeapSelect(a, k) if k = 1 then return minimum(a) create(S) for i from 1 to n insert(S, a) for i from 1 to n/3 x := findmin(S) delete(S, x) xIndex := partition(a, x) // Returns new index of pivot x if k < xIndex softHeapSelect(a, k) else softHeapSelect(a, k-xIndex+1)Read more about this topic: Soft Heap