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

[Timon Gehr via Digitalmars-d]

On 12/01/2015 03:33 AM, Timon Gehr wrote:
> 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.)

(I meant to say: There aren't any assumptions on the initial ordering of 
the array elements.)