An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

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