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

[Andrei Alexandrescu via Digitalmars-d]

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.

Start with a simple array of data. Then mentally decompose that array 
into a concatenation of smaller arrays: first has size 1, second has 
size 4, third has size 9, then 16, 25, 36, ... Generally the size of 
these imaginary subarrays grows quadratically. And they're adjacent to 
each other. The last array may be incomplete.

Example: we decompose an array of size 35 into: an array of size 1 
followed by arrays of sizes 4, 9, 16, 5 (last being an incomplete 
fragment of an array of size 25).

Now each of these arrays we organize as a max heap. Moreover, we arrange 
data such that the maximums of these heaps are in INCREASING order. That 
means the smallest element of the entire (initial) array is at the first 
position, then followed by the next 4 smallest organized in a max heap, 
followed by the next 9 smallest organized in a max heap, ... etc. There 
are a total of O(sqrt n) heaps, and each has O(sqrt n) elements.

That's the layout! Now, to search we look at one heap at a time. 
Whenever the maximum element (first element in the subarray) is smaller 
than the searched value, we skip over that entire heap and go to the 
next one. In the worst case we'll skip O(sqrt n) heaps. When the max 
value in a heap is less than the searched element, we found the heap and 
we run a linear search among O(sqrt n) elements.

The structure is nice for sorting and in particular parallel sorting 
because each subarray can be sorted independently - there's no migration 
into or out of each subarray. Inside each subarray, of course heapsort 
would be a good choice because it takes advantage of the existing max 
heap. 	

I haven't worked out the math for insertion and deletion yet, but they 
seem to also be around O(sqrt n) or O(log(n) * sqrt(n)). Just wanted to 
share with you and discuss what seems to be an interesting data structure.

Please share any thoughts!


Andrei