Note how you can find the median asymptotically faster than do a half-sort. Indeed, the c++ stdlib has functions both for half-sort and for median.

If you want to find the median fast, see Re: Puzzle: The Ham Cheese Sandwich cut. and other nodes in its thread (that thread has an easy to remember title). If you want to do a half-sort with a heap, see Binary heap, but it actually also works to just find the median, partition the elements to ones greater and lessequal to it, and then sort one of the halves.