Extracting Sorted Storage from BinaryHeap

Ivan Kazmenko via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Sun Mar 29 14:33:52 PDT 2015


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.


More information about the Digitalmars-d-learn mailing list