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

[Timon Gehr via Digitalmars-d]

On 11/30/2015 09:57 PM, Andrei Alexandrescu wrote:
> So now consider my square heaps. We have O(n) build time (just a bunch
> of heapifications) and O(sqrt n) search.

How do you build in O(n)? (The initial array is assumed to be completely 
unordered, afaict.)