Develop an algorithm that finds the k th smallest element of a sequence that is
ID: 3748534 • Letter: D
Question
Develop an algorithm that finds the k
th smallest element of
a sequence that is presented to you one element at a time in an order you
cannot control. You have only space O(k) available. This models a situation
where voluminous data arrives over a network or at a sensor. (a)Refine your
algorithm so that it achieves a running time O(nlogk). (b) Refine the algo-
rithm and its analysis further so that your algorithm runs in average-case
time O(n) if k = O(n/logn). Here, average means that all orders of the
elements in the input sequence are equally likely.
Explanation / Answer
a) Please find the algorithm below.
1. Construct a max-heap of size k.
2. Insert the first k elements of the infinite array A[0.....k-1] into the max-heap.
3. Then for each of the remaining elements of the array A[k.....n-1], do the following:
4. Now, we are left with the k-smallest element in the max-heap and the kth smallest element is given by the root of the tree.
Time complexity: This algorithm takes O(nlogk).
b) Please find the modified algorithm below.
ALGORITHM
===================
1. Construct a min-heap and insert all the n elements into it.
2. Clearly, the root of the min-heap will store the smallest element. Hence, remove the first (k-1) elements from the min-heap. This will remove the first (k-1) smallest elements.
3. Now, the root of the min-heap will contains the kth smallest element.
Time complexity: The average-case running time of this algorithm is 0(n + klogn). If k = n/logn, then running-time complexity is O(n + n) ~ O(n).
Please find the corresponding code below in C++.
CODE
=================
// A C++ program to find k'th smallest element using min heap
#include<iostream>
#include<climits>
using namespace std;
// Prototype of a utility function to swap two integers
void swap(int *x, int *y);
// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); //To minheapify 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 extractMin(); // extracts root (minimum) element
int getMin() { return harr[0]; } // Returns minimum
};
MinHeap::MinHeap(int a[], int size)
{
heap_size = size;
harr = a; // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}
// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size == 0)
return INT_MAX;
// Store the minimum 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];
MinHeapify(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 MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}
// 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 smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Build a heap of n elements: O(n) time
MinHeap mh(arr, n);
// Do extract min (k-1) times
for (int i=0; i<k-1; i++)
mh.extractMin();
// Return root
return mh.getMin();
}
// 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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.