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
