algorithm - complexity analysis of kth smallest element in min heap -
i working on find kth smallest element in min heap. have got code complexity o(k log k). tried improve o(k).
below code.
struct heap{ int *array; int count; int capacity; }; int kthsmallestelement(struct heap *h,int i,int k){ if(i<0||i>=h->count) return int_min; if(k==1) return h->array[i]; k--; int j=2*i+1; int m=2*i+2; if(h->array[j] < h->array[m]) { int x=kthsmallestelement(h,j,k); if(x==int_min) return kthsmallestelement(h,m,k); return x; } else { int x=kthsmallestelement(h,m,k); if(x==int_min) return kthsmallestelement(h,j,k); return x; } } my code traversing k elements in heap , complexity o(k). correct?
your code, , in fact, entire approach - wrong, iiuc.
in classic min-heap, thing know each path root children non-decreasing. there no other constraints, in particular no constraints between paths.
it follows k-th smallest element can anywhere in first 2k element. if using entire heap's array built & maintained using classic heap algorithm, solution ω(min(n, 2k)). below require additional requirements on array's structure, additional data structure, or both.
Comments
Post a Comment