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 [1].)

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.

[1]
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]);
}
}
}

```