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