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

[Torin via Digitalmars-d]

On Monday, 30 November 2015 at 23:19:44 UTC, Titus Nicolae wrote:
> On Monday, 30 November 2015 at 20:13:15 UTC, Andrei 
> Alexandrescu wrote:
> ...
>> smallest organized in a max heap, ... etc. There are a total 
>> of O(sqrt n) heaps, and each has O(sqrt n) elements.
> ...
>
> Hi Andrei,
> If I'm not mistaken, the number of heaps is proportional to 
> n^(1/3) not n^(1/2)
> 1+2^2+..+n^2 is proportional to n^3
> https://en.wikipedia.org/wiki/Square_pyramidal_number
> If n heaps have n^3 elements, rewrite n^3=m, then m elements 
> will be stored in m^(1/3) heaps
> Interesting data structure! need to look over the details some 
> more
> Titus

I think Titus and I noticed the same thing at the same time.

You could achieve O(sqrt n) lookup time by having each heap 
contain ceil(sqrt(n)) elements (except for the last one), giving 
you O(sqrt n) heaps of size O(sqrt n), but it may make insertion 
trickier as you try to keep the heaps the same size.