Question

Describe an algorithm that selects and sorts k smallest elements from an array A of length n of integers. Estimate the running time. The efficiency of your algorithm is important.

Answer 1

#include <iostream>
using namespace std;

// Swap function to interchange
// the value of variables x and y
int swap(int& x, int& y)
{
   int temp = x;
   x = y;
   y = temp;
}

// Max Heap Class
// arr holds reference to an integer
// array size indicate the number of
// elements in max Heap
class MaxHeap {

   int size;
   int* arr;

public:
   // Constructor to initialize the size and arr
   MaxHeap(int size, int input[]);

   // Min Heapify function, that assumes that
   // 2*i+1 and 2*i+2 are min heap and fix the
   // heap property for i.
   void heapify(int i);

   // Build the min heap, by calling heapify
   // for all non-leaf nodes.
   void buildHeap();
};

// Constructor to initialize data
// members and creating mean heap
MaxHeap::MaxHeap(int size, int input[])
{
   // Initializing arr and size

   this->size = size;
   this->arr = input;

   // Building the Min Heap
   buildHeap();
}

// Min Heapify function, that assumes
// 2*i+1 and 2*i+2 are min heap and
// fix min heap property for i

void MaxHeap::heapify(int i)
{
   // If Leaf Node, Simply return
   if (i >= size / 2)
       return;

   // variable to store the largest element
   // index out of i, 2*i+1 and 2*i+2
   int largest;

   // Index of left node
   int left = 2 * i + 1;

   // Index of right node
   int right = 2 * i + 2;

   // Select minimum from left node and
   // current node i, and store the minimum
   // index in smallest variable
   largest = arr[left] > arr[i] ? left : i;

   // If right child exist, compare and
   // update the smallest variable
   if (right < size)
       largest = arr[right] > arr[largest]
                           ? right : largest;

   // If Node i violates the min heap
   // property, swap current node i with
   // smallest to fix the min-heap property
   // and recursively call heapify for node smallest.
   if (largest != i) {
       swap(arr[i], arr[largest]);
       heapify(largest);
   }
}

// Build Max Heap
void MaxHeap::buildHeap()
{
   // Calling Heapify for all non leaf nodes
   for (int i = size / 2 - 1; i >= 0; i--) {
       heapify(i);
   }
}

void FirstKelements(int arr[],int size,int k){
   // Creating max Heap for given
   // array with only k elements
   MaxHeap* m = new MaxHeap(k, arr);

   // Loop For each element in array
   // after the kth element
   for (int i = k; i < size; i++) {

       // if current element is smaller
       // than minimum element, do nothing
       // and continue to next element
       if (arr[0] < arr[i])
           continue;

       // Otherwise Change minimum element to
       // current element, and call heapify to
       // restore the heap property
       else {
           arr[0] = arr[i];
           m->heapify(0);
       }
   }
   // Now min heap contains k maximum
   // elements, Iterate and print
   for (int i = 0; i < k; i++) {
       cout << arr[i] << " ";
   }
}
// Driver Program
int main()
{

   int arr[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 };

   int size = sizeof(arr) / sizeof(arr[0]);

   // Size of Min Heap
   int k = 3;

   FirstKelements(arr,size,k);

   return 0;
}

Use Max Heap.

1) Build a Max Heap MH 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 the root of MH.
……a) If the element is greater than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*logk)

3) Finally, MH has k largest elements and root of the MH 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)