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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/2015 06:19 PM, 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

Yes, thanks! I just wrote about this on reddit (before having seen 
this). -- Andrei