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
