Determine k largest elements in from a set of n elements. Our professor hasn\'t

ID: 643933 • Letter: D

Question

Determine k largest elements in from a set of n elements. Our professor hasn't offered much help and I'm super confused on how to even start. Can anyone help me get on the right path please? Thank you!!

3. Consider the problem of determining the k largest elements from a set of n elements. One approach is to sort the data in O(n lg n) time and then just read off the k largest. elements from the sorted list. Another approach is to use a heap. You can run BUILDMAXHEAP on n elements in O(n) time md then call HEAPEXTRACTMAX k times giving you an algorithm with an O(n + k lg n) running time. I'd like von to develop an O(k + (n - k) lg k) solution using heaps. Describe your solution and justify its correctness.

Explanation / Answer

A Simple Solution is to sort the given array using a O(nlogn) sorting algorithm like Merge Sort,Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(nLogn).

// Simple C++ program to find k'th smallest element

#include<iostream>

#include<algorithm>

using namespace std;

// Function to return k'th smallest element in a given array

int kthSmallest(int arr[], int n, int k)

{

// Sort the given array

sort(arr, arr+n);

// Return k'th element in the sorted array

return arr[k-1];

}

// Driver program to test above methods

int main()

{

int arr[] = {12, 3, 5, 7, 19};

int n = sizeof(arr)/sizeof(arr[0]), k = 2;

cout << "K'th smallest element is " << kthSmallest(arr, n, k);

return 0;

}

Method 2 (Using Min Heap