digitalmars.D.learn - Extracting Sorted Storage from BinaryHeap
- =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= (11/11) Mar 29 2015 What's the most efficient way to extract a the storage from a
- Ivan Kazmenko (15/26) Mar 29 2015 Algorithm-wise, you can repeat the following:
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; } ?
Mar 29 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.
Mar 29 2015