The Art Gallery Guardian

Soft heap and selection


I enjoyed the workshop SOSA a lot (Disclaimer: I have a paper in SOSA). The papers are simple and fun. I liked the paper [1] the most, because I learned some really interesting tricks with soft heap.

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 ε\e.
  • 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.

The operation insert takes O(1)O(1) time, extract-min() takes O(1/ε)O(1/\e) time. In this article, we can assume ε=1/4\e=1/4.

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 II insertions into the soft heap, then at most \eI\eI elements can be corrupted.

Although extract-min() might return an element that is not necessarily the minimum, but there is a bound on the amount of possible errors. Before [1], 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 (1ε)n/2(1-\e)n/2 times, and find the maximum element ee. One can see the rank of ee lies between (1ε)n/2(1-\e)n/2 and (1+ε)n/2(1+\e)n/2. Now we can use this to remove at least (1ε)n/2=1+ε2n(1-\e)n/2=\frac{1+\e}{2} n elements, and recurse on the remaining. Once there is only a constant number of elements, use brute force. This gives us an running time T(n)=O(n)+T(1+ε2n)=O(n)T(n) = O(n) + T(\frac{1+\e}{2} n) = O(n).

2 Linear time selection in heap

We are given a min heap HH, and interested in find the kkth smallest element in the heap. We first insert the min element ee into the soft heap.

Whenever we apply extract-min to the soft heap, we obtain ee and a set of newly corrupted elements CC. For each element eCe'\in C, we add the children of ee' in HH into the soft heap. If ee is not corrupted, we also add the children of ee in HH into the soft heap. Once we apply extract-min k1k-1 times we stop. Let SS be the set of all elements that was inserted into the soft heap. There are two important claims: S=O(k)|S|=O(k) and the rank kk element has to be in SS. We can use a linear time selection algorithm on SS 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 kk element in mm sorted lists, and selecting kkth element in X+Y={x+yxX,yY}X+Y = \set{x+y | x\in X, y\in Y}.

References

[1] 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.

Posted by Chao Xu on 2019-01-22.
Tags: algorithm, data structure.