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

[Andrei Alexandrescu via Digitalmars-d]

On 11/30/15 9:47 PM, Timon Gehr wrote:
> 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.)

That's quite challenging. (My O(n) estimate was off the cuff and 
possibly wrong.) Creating the structure entails simultaneously solving 
the selection problem (find the k smallest elements) for several values 
of k. I'll post here if I come up with something. -- Andrei