CODEWITHSUNDEEP
algorithmheap
Vasu Dev Garg
Vasu Dev Garg

Reputation: 121

complexity analysis of kth smallest element in min heap

I am working on to find the kth smallest element in min heap. I have got a code for this whose complexity is O(k log k). I tried to improve it to O(k).
Below is the 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 is traversing k elements in heap and thus complexity is O(k). Is it correct?

Upvotes: 0

Views: 393

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76316

Your code, and in fact, its entire approach - are completely wrong, IIUC.

In a classic min-heap, the only thing you know is that each path from the root to the children is non-decreasing. There are no other constraints, in particular no constraints between the paths.

It follows that the k-th smallest element can be anywhere in the first 2k element. If you are just using the entire heap's array built & maintained using the classic heap algorithm, any solution will necessarily be Ω(min(n, 2k)). Anything below that will require additional requirements on the array's structure, an additional data structure, or both.

Upvotes: 2

Related Questions