K’th Smallest/Largest Element in Unsorted Array (Using Max-Heap)

Software Development
#1

Hello Everyone,

Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Method (Using Max-Heap)
We can also use Max Heap for finding the k’th smallest element. Following is an algorithm.

  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 k’th element (arr[k] to arr[n-1]), compare it with root of MH.
    ……a) If the element is less 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, the root of the MH is the kth smallest element.
    Time complexity of this solution is O(k + (n-k)*Logk)

The following is C++ implementation of the above algorithm

// A C++ program to find k'th smallest element using max heap

#include <climits>

#include <iostream>

using namespace std;

// Prototype of a utility function to swap two integers

void swap( int * x, int * y);

// A class for Max Heap

class MaxHeap {

int * harr; // pointer to array of elements in heap

int capacity; // maximum possible size of max heap

int heap_size; // Current number of elements in max heap

public :

MaxHeap( int a[], int size); // Constructor

void maxHeapify( int i); // To maxHeapify subtree rooted with index i

int parent( int i) { return (i - 1) / 2; }

int left( int i) { return (2 * i + 1); }

int right( int i) { return (2 * i + 2); }

int extractMax(); // extracts root (maximum) element

int getMax() { return harr[0]; } // Returns maximum

// to replace root with new node x and heapify() new root

void replaceMax( int x)

{

harr[0] = x;

maxHeapify(0);

}

};

MaxHeap::MaxHeap( int a[], int size)

{

heap_size = size;

harr = a; // store address of array

int i = (heap_size - 1) / 2;

while (i >= 0) {

maxHeapify(i);

i--;

}

}

// Method to remove maximum element (or root) from max heap

int MaxHeap::extractMax()

{

if (heap_size == 0)

return INT_MAX;

// Store the maximum vakue.

int root = harr[0];

// If there are more than 1 items, move the last item to root

// and call heapify.

if (heap_size > 1) {

harr[0] = harr[heap_size - 1];

maxHeapify(0);

}

heap_size--;

return root;

}

// A recursive method to heapify a subtree with root at given index

// This method assumes that the subtrees are already heapified

void MaxHeap::maxHeapify( int i)

{

int l = left(i);

int r = right(i);

int largest = i;

if (l < heap_size && harr[l] > harr[i])

largest = l;

if (r < heap_size && harr[r] > harr[largest])

largest = r;

if (largest != i) {

swap(&harr[i], &harr[largest]);

maxHeapify(largest);

}

}

// A utility function to swap two elements

void swap( int * x, int * y)

{

int temp = *x;

*x = *y;

*y = temp;

}

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

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

{

// Build a heap of first k elements: O(k) time

MaxHeap mh(arr, k);

// Process remaining n-k elements. If current element is

// smaller than root, replace root with current element

for ( int i = k; i < n; i++)

if (arr[i] < mh.getMax())

mh.replaceMax(arr[i]);

// Return root

return mh.getMax();

}

// Driver program to test above methods

int main()

{

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

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

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

return 0;

}

Output:

K’th smallest element is 12