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

[Timon Gehr via Digitalmars-d]

On 12/03/2015 11:44 PM, Andrei Alexandrescu wrote:
> 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,

There was actually an (asymptotically inconsequential) error in the 
initial expression. Fixed version:

Ignoring the work performed in the heaps each elements starts in (which 
is obviously at most O(n)), we can lower bound the performed work; for 
the heap of size j, we sift j elements down all the following heaps of 
sizes i=j+2,i=j+4,…,i=m).


∑ⱼ[j∈{1,3,…,m}]·j·∑ᵢ[i∈{j+2,j+4,…,m}]·log(i)
=
∑ᵢ∑ⱼ[j∈{1,3,…,m}]·[i∈{j+2,j+4,…,m}]·j·log(i)
=
∑ᵢ∑ⱼ∑ₖ∑ₗ[i=2·k+1]·[j=2·l+1]·[1≤j≤m]·[j+2≤i≤m]·j·log(i)
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ⱼ∑ₗ[j=2·l+1]·[1≤j≤m]·[j+2≤i]·j
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ⱼ∑ₗ[j=2·l+1]·[1≤j≤i-2]·j
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ⱼ∑ₗ[j=2·l+1]·[1≤2·l+1≤i-2]·(2·l+1)
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ₗ[1≤2·l+1≤i-2]·(2·l+1)
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ₗ[0≤l≤(i-3)/2]·(2·l+1)
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·∑ₗ[0≤l≤(i-3)/2]·(2·l+1)
=
∑ᵢ∑ₖ[i=2·k+1]·[3≤i≤m]·log(i)·((i-1)/2)²
=
∑ₖ[3≤2·k+1≤m]·log(2·k+1)·k²
=
∑ₖ[1≤k≤(m-1)/2]·log(2·k+1)·k²
≥
Ω(m³)
=
Ω(n^(3/2)).



Less formally:

The heap of size 3 is sifted through by 1=1² element from the first heap.
The heap of size 5 is sifted through by 1+3=2² elements from the first 
and second heaps
The heap of size 7 is sifted through by 1+3+5=3² elements from the first 
three heaps.
...
The heap of size 2·k+1 is sifted through by k² elements.
...
The heap of size m is sifted through by ((m-1)/2)² elements.

This gives the last sum in the above derivation:

      sifting through heap of size 2·k+1 costs at least log(2·k+1)
                                 v
         ∑ₖ[1≤k≤(m-1)/2]·log(2·k+1)·k²
              ^
k ranges from 1 to (m-1)/2.

The factor k² is the number of elements sifting through the heap of size 
2·k+1.

The sum can be lower bounded by
1+2²+3²+…+((m-1)/2)²
=
(m+1)·(m-1)·(m-3)/24+(m+1)·(m-1)/8
=
(m³-m)/24
≥
Ω(m³).


> 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.
> ...

That intuition is spot on, but the sorting algorithm that the 
construction algorithm imitates most closely is a version of insertion sort.

> 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.)
> ...

It provides motivation to try and find another construction algorithm 
that runs asymptotically faster than n log n, or to prove that n log n 
is asymptotically optimal.

> At this point I need to either get to the bottom of the math or

The basic argument is not too involved: If each element needs to be 
sifted all the way down to the last heap, then for each of √n̅ heaps, you 
need to sift all its ~√n̅ elements down ~√n̅ other heaps, which requires 
more than ≈n^(3/2) operations. The above derivation makes this rigorous.

> 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.)
> ...

Good point. I had declared victory on the "insert" front too early.