Question

Given an array A[1..n], with distinct values and k with 1 ≤ k ≤ n. We want to return the k smallest element of A[1.....n], in non-decreasing order. For example: A = [5, 4, 6, 2, 10] and k = 4, the algorithm returns [2, 4, 5, 6]. There are at least the following four approaches:

a. heapify A and then extract k elements one by one

b. sort the array (e.g. using MergeSort or HeapSort) and then read the first k elements

c. apply the selection procedure k times to find the 1st, 2nd, · · · , the k’th smallest element;

d. apply the selection procedure to find the k’th smallest element, then use that element to find the k smallest elements, and then sort those k elements.

For each approach, find the asymptotic worst-case running time which should be of the form Θ(f(n, k)).

Now assume k = √ n. Then for each approach express the asymptotic running-time as a function of n only.

e. Implement HeapSort. Write the code in Python IDE, run some test results and discuss if your results are supporting the claim of Θ(n lg n).

f. How does the heapsort perform compared to MergeSort and QuickSort

Answer 1

#include <iostream>
using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
   int largest = i; // Initialize largest as root
   int l = 2 * i + 1; // left = 2*i + 1
   int r = 2 * i + 2; // right = 2*i + 2

   // If left child is larger than root
   if (l < n && arr[l] > arr[largest])
       largest = l;

   // If right child is larger than largest so far
   if (r < n && arr[r] > arr[largest])
       largest = r;

   // If largest is not root
   if (largest != i) {
       swap(arr[i], arr[largest]);

       // Recursively heapify the affected sub-tree
       heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n,int k)
{
   // Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
       heapify(arr, n, i);

   // One by one extract an element from heap
   for (int i = n - 1; i >= 0; i--) {
       // Move current root to end
       swap(arr[0], arr[i]);

       // call max heapify on the reduced heap
       heapify(arr, i, 0);
   }
}

/* A utility function to print array of size n */
void printArray(int arr[], int k)
{
   for (int i = 0; i < k; ++i)
       cout << arr[i] << " ";
   cout << "\n";
}

// Driver program
int main()
{
   int arr[] = { 5, 4, 6, 2, 10 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k=4;
   heapSort(arr, n, k);

   cout << "Sorted array is \n";
   printArray(arr, k);
}