An Optimal Algorithm for Selection in a Min-Heap

AbstractAn 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