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. © 1993 Academic Press, Inc.