What's the most efficient way to extract a the storage from a BinaryHeap and then sort it?

Is there a better way other than

    binaryHeap.release.sort

than makes use of the heap property? For example

    while (!binaryHeap.empty)
    {
        sortedStorage ~= binaryHeap.front;
        binaryHeap.popFront;
    }

?

On Sunday, 29 March 2015 at 20:05:22 UTC, Nordlöw wrote:
> What's the most efficient way to extract a the storage from a BinaryHeap and then sort it?
>
> Is there a better way other than
>
>     binaryHeap.release.sort
>
> than makes use of the heap property? For example
>
>     while (!binaryHeap.empty)
>     {
>         sortedStorage ~= binaryHeap.front;
>         binaryHeap.popFront;
>     }
>
> ?

Algorithm-wise, you can repeat the following:
1. Decrease the length of the heap by one.
2. Swap the first (largest) element with the one just removed.
3. Sift the new first element (which is most surely not largest) down the heap.
The array is sorted in place: the prefix is always a binary heap, and the suffix is always a sorted array.

This is still O(n log n), but may have a lower constant than just sorting the array.  Or it may give no benefit over sort() because sifting down a heap is not as local in memory as quicksort.  A benchmark would show what's best.

Unsure how to express that cleanly with the Phobos implementation of BinaryHeap.

Ivan Kazmenko.