Kth largest element - heap

 Given an array arr[] of N positive integers and a number K. The task is to find the kth largest element in the array.

Example 1:

Input:
5 3
3 5 4 2 9

Output: 
4

lets use a simple method:
1) sort the given array using sorting algorithm like merge,heap sort etc and return the element at index k-1 in the sorted array.

Time Complexity of this solution is O(N Log N)

int kthSmallest(int arr[], int n, int k) 
{ 
          sort(arr, arr + n);            // Sort the given array 
     
 
       return arr[k - 1];    // Return k'th element in the sorted array 
} 

Method 2(Using min Heap)
We can also use min Heap for finding the k’th smallest element. Following is algorithm.
1) Build a min-Heap pq of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of pq.
       a) If the element is greater than the root (pq.top())  ,then insert this element to the heap and remove the root(pq.pop())
        b) Else ignore it.
// The step 2 is O((n-k)*logk)

3) Finally, root of the pq is the kth largest element(pq.top())

Time complexity of this solution is O(k + (n-k)*Logk)

int KthLargest(int arr[], int n, int k) {
    
 priority_queue< int, vector<int>, greater<int> > pq(arr,arr+k);// min heap
for(int i = k; i < n; i++)
{
if(arr[i] >= pq.top())
{
pq.pop();
pq.push(arr[i]);
}
}
return pq.top();
}

method 3 :

step 1: take an array h[] of size 10^5 , and mark the presence of all elements from a[].

step 2: now traverse from the end of the h[] array and take a count variable and when the presence is greater than 1 increment count

step 3: when count is equal to k , return that index from h[] array .

int KthLargest(int arr[], int n, int k)
{
int i;
int h[100001]={0};

for(i=0;i<=n;i++)
h[arr[i]]++;

int count = 0;
for(i=100000;i>=0;i--)
{
if(h[i]>0)
count++;

if(count==k)
return i;
    
}
}

 for kth smallest element similar but reverse procedure as that of kth largest element.