WAP to Find Kth Maximum or Kth Minimum in Array in Linear Time

Other Variation

You have to develop a piece of code that can be attached to a program
like Microsoft Word, which would list the last "N" words of the
document in descending order of their occurrence, and update the list
as the user types. What code would you write? Using pseudo code is
fine, just list the basic things you would consider

Given a stream of distance of millions of stars from the earth, find the nearest n star from the earth.


Algorithm

1) Build a Min 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 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.
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)



Java Code


class Heap_new
{
int arr[]; // pointer to array of elements in heap
int heap_size;
Heap_new()
{

}

Heap_new(int a[], int size)
{
heap_size = size;
arr = a;
}


int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;

void changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void swap(int i,int j)
{
int temp=i;
i=j;
j=temp;
}

void minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
minHeapify(largest);
}
}

void buildminHeap()
{
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap_new hp=new Heap_new(arr,k);
hp.buildminHeap();

int i;
for(i = k; i < n; i++)
{
changeRoot(arr[i]);
}

}

public static void main(String a[])
{
int k = 4;
int arr[] = new int[]{12, 34, 10, 8, 9, 24, 66};
Heap_new h=new Heap_new();
h.kthLargest(arr,arr.length,k);
int i=0;
for(i=0;iSystem.out.println(arr[i]);

}


}



Run Here https://ideone.com/UKAzU

C++ Code for Kth Maximum In Array


#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildminHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}

}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 22, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
kthLargest(arr, n, k);


int i=0;
for(i=0;iprintf(" %d ",arr[i]);

getchar();
return 0;
}


Run here https://ideone.com/f8Or0

C++ Code For Kth Minimum In Array

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildmaxHeap();
void maxHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root > x)
{
arr[0] = x;
}
maxHeapify(0);
}

void Heap::maxHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] >arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
maxHeapify(largest);
}
}

void Heap::buildmaxHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
maxHeapify(i);
i--;
}
}

int kthMinimum(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildmaxHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}
return hp.getRoot();
}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
printf(" %d ", kthMinimum(arr, n, k));
int i=0;
for(i=0;i printf(" %d ",arr[i]);

getchar();
return 0;
}

Run Here https://ideone.com/JIu1s

Source Sandeep
Enjoy