Soft heap and selection
Here I give a teaser of two things soft heap can do.
We consider a minimalistic soft heap, as there are soft heap with more operations.
soft-heap(ε): creates an empty soft heap with error parameter .
insert(e): insert an element into the heap.
extract-min(): return the element of minimum key in heap, and set of newly corrupted elements since last extraction.
insert takes time,
extract-min() takes time. In this article, we can assume .
During each insertion, the key of some elements might be increased. An element is corrupted if its key in the heap is strictly greater than the original key. If there are insertions into the soft heap, then at most elements can be corrupted.
extract-min() might return an element that is not necessarily the minimum, but there is a bound on the amount of possible errors. Before , I don't know of any application of soft heap other than vaguely knowing about it was used for minimum spanning tree.
1 Linear time selection in unordered list
We insert all elements into the soft-heap, and then we apply
extract-min times, and find the maximum element . One can see the rank of lies between and . Now we can use this to remove at least elements, and recurse on the remaining. Once there is only a constant number of elements, use brute force. This gives us an running time .
2 Linear time selection in heap
We are given a min heap , and interested in find the th smallest element in the heap. We first insert the min element into the soft heap.
Whenever we apply
extract-min to the soft heap, we obtain and a set of newly corrupted elements . For each element , we add the children of in into the soft heap. If is not corrupted, we also add the children of in into the soft heap. Once we apply
extract-min times we stop. Let be the set of all elements that was inserted into the soft heap. There are two important claims: and the rank element has to be in . We can use a linear time selection algorithm on once we prove the two claims.
3 Other useful results
There are some other nice results in the paper. Getting optimal results for selecting the rank element in sorted lists, and selecting th element in .
 H. Kaplan, L. Kozma, O. Zamir, U. Zwick, Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps, in: J.T. Fineman, M. Mitzenmacher (Eds.), 2nd Symposium on Simplicity in Algorithms (Sosa 2019), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018: pp. 5:1–5:21 10.4230/OASIcs.SOSA.2019.5.