On Monday, 30 November 2015 at 20:13:15 UTC, Andrei Alexandrescu
wrote:
Now each of these arrays we organize as a max heap. Moreover,
we arrange data such that the maximums of these heaps are in
INCREASING order. That means the smallest element of the entire
(initial) array is at the first position, then followed by the
next 4 smallest organized in a max heap, followed by the next 9
smallest organized in a max heap, ... etc. There are a total of
O(sqrt n) heaps, and each has O(sqrt n) elements.
Isn't the size of each heap a little larger than O(sqrt n)? The
total number of elements you can hold in k heaps is equal to the
kth square pyramidal number, which is of size O(k^3), so the
largest heap is of size k^2 = O(n^(2/3))
