[bwhmather]

The smoothsort variant of heap sort might be a better alternative. It can be implemented in-place like an ordinary heap sort, but unlike an ordinary heap sort the root will be at the end of the heap where you want the elements to end up when they've been popped. The whole array, including the fully sorted part, will remain a valid heap so you can continue to add new elements efficiently.