Kth largest or smallest element in an array

Write an C program to find kth largest element in an array. Elements in array are not sorted.

example, if given array is [1, 3, 12, 19, 13, 2, 15] and you are asked for the 3rd largest element i.e., k = 3 then your program should print 13.

Method 1

Use sorting. Return first k elements of this array or kth element of sorted array whatever required.

Method 2 (Using temporary array of size K)

1) Store the first k elements in a temp array temp[0..k-1].
2) Find the smallest element in temp[].
3) For each element x in arr[k] to arr[n-1]
If x is greater than the minimum then remove minimum element and insert x.
4) Print final k elements of temp[]

Time Complexity: O((n-k)*k).

If we want the kth Largest only then sort the array and get kth largest then complexity O((n-k)*k + klogk)

Method 3 (Using quick sort)

We could approach it in the same way in which QUICKSORT algorithm approaches the sorting problem.

1. Pick an element within current segment
   and call it the pivot

2. Count elements that are smaller and
   elements that are larger than the pivot

3. If number of elements smaller than the pivot
   is larger than K, then move those elements
   to the beginning of the array and run
   the algorithm recursively only on that part of the array.

4. Otherwise, if number of elements smaller than the pivot
   plus number of elements equal to the pivot is larger
   than K, then Kth element is equal to pivot
   so just return the pivot and finish.

5. Otherwise, move all elements larger than the pivot
   to the beginning of the array and run the algorithm
   recursively only on that part of the array.

Method 4 (Using min heap)

This method is modification and optimization of method 2.
1) Build a Min Heap of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)

2) 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. The step 2 is O((n-k)*logk)
3) Finally, min heap has k largest elements and root of the min heap is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)

All of the above methods can be used to find the kth largest (or smallest) element.

Implementation of min heap method:

#include<stdio.h>
 
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; 
    int r = 2*i+1;
    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]; 
}
 
 
int main() { 
	int a[] = {16,17,18,4,12,9,5,1}; 
	int size = sizeof(a)/sizeof(a[0]); 
	int k = 3; 
	printf("%d ",kthLargest(a,size,k));
	return 0; 
}

output 16