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.
