C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Find kth Largest Element in a Sequence



C++ Program to Find kth Largest Element in a Sequence

- Extract the Kth largest element from a sequence.
- By selectively sorting the array to get Kth largest element it has the complexity of O(k*n).
- We can improve the time complexity by approaching the problem using max-heap.
- The time complexity is O(n+k*log(n)).

- Approach the solution using max heap technique.
- Build the max heap k times.
- In each iteration pop max of the heap out of the sequence.
- Display the Kth max of the heap.
- Exit.

#include <iostream>
 
using namespace std;
 
// A function to heapify the array.
void MaxHeapify(int a[], int i, int n)
{
	int j, temp;
	temp = a[i];
	j = 2*i;
 
	while (j <= n)
	{
		if (j < n && a[j+1] > a[j])
			j = j+1;
		// Break if parent value is already greater than child value.
		if (temp > a[j])
			break;
		// Switching value with the parent node if temp < a[j].
		else if (temp <= a[j])
		{
			a[j/2] = a[j];
			j = 2*j;
		}
	}
	a[j/2] = temp;
	return;
}
 
// A function to build max heap from the initial array by checking all non-leaf node to satisfy the condition.
void Build_MaxHeap(int a[], int n)
{
	int i;
	for(i = n/2; i >= 1; i--)
		MaxHeapify(a, i, n);
}
 
int main()
{
	int n, i, temp, k;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
	n++;
	int arr[n];
	for(i = 1; i < n; i++)
	{
		cout<<"Enter element "<<i<<": ";
		cin>>arr[i];
	}
 
	cout<<"\nEnter the k value: ";
	cin>>k;
 
	Build_MaxHeap(arr, n-1);
 
	// Build max-heap k times, extract the maximum and store it in the end of the array.
	for(i = n-1; i >= n-k; i--)
	{
		temp = arr[i];
		arr[i] = arr[1];
		arr[1] = temp;
		MaxHeapify(arr, 1, i - 1);
	}
 
	// Printing the array state.
	cout<<"\nAfter max-heapify the given array "<<k<<" times the array state is: ";
	for(i = 1; i < n; i++)
		cout<<"->"<<arr[i];
 
	// The Kth largest element.
	cout<<"\n\nThe "<<k<<"th largest element is: "<<arr[n-k];
	return 0;
}