An optimal algorithm for selection in a min-heap

DOI10.1006/inco.1993.1030zbMath0818.68065OpenAlexW2111340560WikidataQ56049346 ScholiaQ56049346MaRDI QIDQ2366561

Greg N. Frederickson

Publication date: 30 August 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1993.1030

zbMATH Keywords

implicit data structures\(k^{th}\) smallest elementmin-heap

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Finding the k shortest paths in parallel, Space-Efficient Frameworks for Top- k String Retrieval, Algorithms for proximity problems in higher dimensions, Encoding two-dimensional range top-\(k\) queries, A nearly optimal randomized algorithm for explorable heap selection, Dynamic data structures for \(k\)-nearest neighbor queries, Unnamed Item, K\(^{\ast}\): A heuristic search algorithm for finding the \(k\) shortest paths, Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths, Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence, Optimal deterministic shallow cuttings for 3-d dominance ranges, Faster shortest-path algorithms for planar graphs, Algorithms for Problems on Maximum Density Segment, A new $O(m+k n log overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs, Unnamed Item, Construction of the similarity matrix for the spectral clustering method: numerical experiments, Finding the k Shortest Paths, A Survey on Priority Queues