# 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 :**

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; } }