Abstract
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 worst-case linear selection algorithm,which is
simply implemented and uses binary heap construction as its principal engine.
The algorithm is implemented in place, and shown to perform similarly to
in-place median of medians.