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

[Titus Nicolae 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

This might give a better balanced structure.

Sum of odd numbers 1+3+5+..+(2n-1) = n^2
For N total elements, there are sqrt(n) heaps, and 2*sqrt(n) 
elements in the largest heap
@Andrei: La multi ani! :)