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
