An optimal algorithm for selection in a min-heap
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.
- Reflected min-Max heaps
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- Algorithms for proximity problems in higher dimensions
- Construction of the similarity matrix for the spectral clustering method: numerical experiments
- A selectable sloppy heap
- Encoding two-dimensional range top-\(k\) queries
- Algorithms for problems on maximum density segment
- A survey on priority queues
- Space-efficient frameworks for top-k string retrieval
- scientific article; zbMATH DE number 140493 (Why is no real title available?)
- K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths
- Finding the k Shortest Paths
- Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
- On solving probabilistic linear Diophantine equations
- Finding the \(k\) shortest paths in parallel
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- A new \(O(m+k n \log \overline{d})\) algorithm to find the \(k\) shortest paths in acyclic digraphs
- Optimal incremental sorting
- Faster shortest-path algorithms for planar graphs
- A nearly optimal randomized algorithm for explorable heap selection
- Dynamic data structures for \(k\)-nearest neighbor queries
- Selection from heaps, row-sorted matrices, and X+Y using soft heaps
- A nearly optimal randomized algorithm for explorable heap selection
- Dynamic unit-disk range reporting
- Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
- On sorting, heaps, and minimum spanning trees
This page was built for publication: An optimal algorithm for selection in a min-heap
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366561)
