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