An optimal algorithm for selection in a min-heap (Q2366561)

The paper considers the problem of selecting the \(k^{th}\) smallest element in a min-heap of \(n\) elements (i.e., \(x_ i > x_{\lfloor i/2 \rfloor}\) holds for \(i = 1, \dots, n)\) when \(n \gg k\). It is shown that this is possible in \({\mathcal O} (k)\) time. The technique used is rather interesting in itself: clusters (called clans) are formed incrementally; forming clans means partitioning the heap into groups of \(\lfloor \log k \rfloor\) elements such that the first clan contains the first \(\lfloor \log k \rfloor\) elements, the second clan contains the next \(\lfloor \log k \rfloor\) elements, etc. The largest elements of a clan are maintained in an auxiliary heap. This construction leads to a \({\mathcal O} (k \log \log k)\) algorithm which is refined in a sequence of steps yielding the main result of this paper. Two applications are discussed in the Introduction: selecting the \(k\) smallest spanning trees of a weighted undirected graph, and a resource allocation problem.