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

[H. S. Teoh via Digitalmars-d]

On Mon, Nov 30, 2015 at 03:13:11PM -0500, Andrei Alexandrescu via Digitalmars-d wrote:
> Okasaki's book is a continued inspiration of data structures and
> algorithms.
> 
> I was thinking along the following lines: typical collections are
> searchable in linear time. Then we have highly structured collections
> that feature logarithmic search time. But there seems to be nothing in
> between. So I was thinking, what would be a data structure that allows
> O(sqrt n) search times?
> 
> After a little tinkering, here's what I came up with.

Interesting indeed.

It leaves me wondering, though, what's the point of having an O(sqrt n)
collection? What are the advantages?  Why would I use this structure
instead of, say, a traditional array heap with O(log n) search time?


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson