An Optimal Algorithm for Selection in a Min-Heap

An O(k)-time algorithm is presented for selecting the kth smallest element in a binary min-heap of size n⪢k. The approach uses recursively defined data structures that impose a hierarchical grouping on certain elements in the heap. The result establishes a further example of a partial order for which the kth smallest element can be determined in time proportional to the information theory lower bound. Two applications, to a resource allocation problem and to the enumeration of the k smallest spanning trees, are identified.

Authors

• G.N. Frederickson

Keywords

No keywords are indexed for this paper.