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.
