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

[Timon Gehr via Digitalmars-d]

On 12/01/2015 11:48 PM, Andrei Alexandrescu wrote:
> On 12/01/2015 12:13 AM, Andrei Alexandrescu wrote:
>> On 11/30/15 9:47 PM, Timon Gehr wrote:
>>> On 12/01/2015 03:33 AM, Timon Gehr wrote:
>>>> On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
>>>>> So now consider my square heaps. We have O(n) build time (just a bunch
>>>>> of heapifications) and O(sqrt n) search.
>>>>
>>>> How do you build in O(n)? (The initial array is assumed to be
>>>> completely
>>>> unordered, afaict.)
>>>
>>> (I meant to say: There aren't any assumptions on the initial ordering of
>>> the array elements.)
>>
>> That's quite challenging. (My O(n) estimate was off the cuff and
>> possibly wrong.) Creating the structure entails simultaneously solving
>> the selection problem (find the k smallest elements) for several values
>> of k. I'll post here if I come up with something. -- Andrei
>
> OK, I think I have an answer to this in the form of an efficient algorithm.
>
> First off: sizes 1+3+5+7+... seem a great choice, I'll use that for the
> initial implementation (thanks Titus!).
>
> Second: the whole max heap is a red herring - min heap is just as good,
> and in fact better. When doing the search just overshoot by one then go
> back one heap to the left and do the final linear search in there.
>
> So the structure we're looking at is an array of adjacent min-heaps of
> sizes 1, 3, 5, etc. The heaps are ordered (the maximum of heap k is less
> than or equal to the minimum of heap k+1). Question is how do we build
> such an array of heaps in place starting from an unstructured array of
> size n.
>
> One simple approach is to just sort the array in O(n log n). This
> satisfies all properties - all adjacent subsequences are obviously
> ordered, and any subsequence has the min heap property. As an
> engineering approach we may as well stop here - sorting is a widely
> studied and well implemented algorithm. However, we hope to get away
> with less work because we don't quite need full sorting.
>
> Here's the intuition: the collection of heaps can be seen as one large
> heap that has a DAG structure (as opposed to a tree). In the DAG, the
> root of heap k+1 is the child of all leaves of heap k (see
> http://imgur.com/I366GYS which shows the DAG for the 1, 3, 7, and 7 heaps).
>
> Clearly getting this structure to respect the heap property is all
> that's needed for everything to work - so we simply apply the classic
> heapify algorithm to it. It seems it can be applied almost unchanged -
> starting from the end, sift each element down the DAG.
>
> This looks efficient and minimal; I doubt there's any redundant work.
> However, getting bounds for complexity of this will be tricky. Classic
> heapify is tricky, too - it seems to have complexity O(n log n) but in
> fact has complexity O(n) - see nice discussion at
> http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity.
> When applying heapify to the DAG, there's more restrictions and the
> paths are longer, so a sliver more than O(n) is expected.
>
> Anyway, this looks ready for a preliminary implementation and some more
> serious calculations.
>

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.

For simplicity, let's assume that n = m² for m odd, such that the sizes 
of the heaps are 1,3,…,m. To sift some element down one entire heap of 
size i takes ≥ log₂(i) steps.

Ignoring the work performed in the heaps each elements starts in (which 
is obviously at most O(n) in total), 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+1,i=j+2,…,i=m:

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

I.e. sorting is asymptotically faster, and probably also in practice. 
Moreover, the construction algorithm would be slower even if sifting 
down one entire heap would run in constant time.

However, for your adapted data structure with min-heaps, implementing 
insert and remove in O(√n̅ log n) is now easy using your "sifting in a 
DAG" approach.

One way to prove a useful lower bound on the time it must take to build 
might be to observe that building recursively can be used for sorting.

> One more interesting thing: the heap heads are sorted, so when
> searching, the heap corresponding to the searched item can be found
> using binary search. That makes that part of the search essentially
> negligible - the lion's share will be the linear search on the last
> mile. In turn, that suggests that more heaps that are smaller would be a
> better choice. (At an extreme, if we have an array of heaps each
> proportional to log(n), then we get search time O(log n) even though the
> array is not entirely sorted.)
>
>
> Andrei
>

The linear search can have way better locality, so it is likely that 
actually the binary search dominates for some data sets.