On 12/02/2015 06:26 AM, Timon Gehr wrote:
Assume the initial array is sorted from largest to smallest. This will be the worst case for this construction algorithm, as each element will be sifted all the way down to leaf level of the last heap.
[...]
Ω(n^(3/2)).
Thanks. My math-fu is not good enough to properly follow the argument, but that bound sounds high; one intuition is that there shouldn't be more work done than in sorting - fewer swaps, fewer comparisons, less resulting structure.
For example, heapifying the array 1, 2, 3, 4, 5, 6, 7, 8, 9 in 1+3+5 max heaps results in the array 9, 8, 6, 7, 5, 4, 3, 2, 1 which is "less sorted" than the fully sorted array. (I know, that doesn't prove anything.)
At this point I need to either get to the bottom of the math or put together an experimental rig that counts comparisons and swaps.
(BTW I figured one reason for which these DAG heaps work at all is that there's never a need to sift an element up between heaps; that would be inefficient because the root of a subheap has multiple parents. Sifting down is efficient because each node has at most two children.)
Andrei
