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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/2015 06:32 PM, Titus Nicolae wrote:
> 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! :)

This is very interesting. Thanks, and thanks! -- Andrei