Re: 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.)