Find k largest(or smallest) elements in an array. No sorting allowed

Min Heap method

• Build a Min Heap of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
• For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of min heap.
  If the element is greater than the root then make it root and call heapify for min heap.
  else ignore it. O((n-k)*logk)
• Finally, min heap has k largest elements and root of the min heap is the kth largest element.
  O(k + (n-k)Logk) without sorted output.
• If sorted output is needed then O(k + (n-k)Logk + kLogk)

void swap(int *a, int *b)
    {
        *a = *a + *b;
        *b = *a - *b;
        *a = *a - *b;
    }
      
    void minHeapify(int a[], int size, int i)
    {
        int l = 2*i + 1; //using zero based arrays
        int r = 2*i + 2;
        int smallest = i;
        if(l<size && a[l]<a[smallest])
            smallest = l;
        if(r<size && a[r]<a[smallest])
            smallest = r;
        if(smallest!=i)
        {
            swap(&a[i],&a[smallest]);
            minHeapify(a,size,smallest);
        }   
    }
       
    void buildMinHeap(int a[], int size) {
        for(int i=size/2;i>=0;i--)
            minHeapify(a,size,i);  
    }
       
    int kthLargest(int a[], int size, int k)
    {
        int minHeap[k];
        int i;
        for(i=0;i<k;i++)
            minHeap[i] = a[i];
        
        buildMinHeap(minHeap,k);
        for(i=k;i<size;i++)
        {
            if(a[i]>minHeap[0])
            {
                minHeap[0]=a[i];
                minHeapify(minHeap,k,0);
            }
        }
        return minHeap[0];
    }