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

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Mon Nov 30 18:22:15 PST 2015

```On 11/30/2015 09:13 PM, Andrei Alexandrescu wrote:
> 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)).

(Assuming the bucket sizes actually grow linearly.) It seems to me that
for insertion O(√n̅ log n) is very easy to achieve, but not for deletion.
(For insertion, one simple strategy that satisfies the bound is to
repeatedly move the maximum to the next heap .)

Deletion leaves a hole in one heap, which should be filled by the
minimum element of the next heap, etc. The minimum cannot be extracted
efficiently from a max-heap.


struct Fancy(T){
T[] a;
void insert(T t){
size_t i=1,j=0;
for(;j+i<=a.length;j+=i,i++){
if(!(t<a[j])) continue;
swap(t,a[j]);
for(size_t c=0,w=1;w<i;c=w,w=2*c+1){
if(w+1<i&&a[j+w]<a[j+w+1]) w++;
if(!(a[j+c]<a[j+w])) break;
swap(a[j+c],a[j+w]);
}
}
a~=t;
for(auto c=a.length-1-j;c;c/=2){
if(!(a[j+c/2]<a[j+c])) break;
swap(a[j+c/2],a[j+c]);
}
}
}

```