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

[Timon Gehr via Digitalmars-d]

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