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

[Torin via Digitalmars-d]

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))