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

Timon Gehr via Digitalmars-d digitalmars-d at
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.

struct Fancy(T){
   T[] a;
   void insert(T t){
     size_t i=1,j=0;
       if(!(t<a[j])) continue;
       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;
     for(auto c=a.length-1-j;c;c/=2){
       if(!(a[j+c/2]<a[j+c])) break;

More information about the Digitalmars-d mailing list