Median of heaps: linear-time selection by recursively constructing binary heaps

Oliver Serang

The first worst-case linear-time algorithm for selection was discovered in 1973; however, linear-time binary heap construction was first published in 1964. Here we describe another…