import java.util.Arrays;
import java.util.stream.Stream;
class Solution {
public static void main(String[] args){
int arr[] = new int[]{5,2,3,8,7,1,6};
System.out.println(Arrays.toString(arr));
//some test cases to check
System.out.println(getKLargest(arr, 1));
System.out.println(getKLargest(arr, 2));
System.out.println(getKLargest(arr, 3));
System.out.println(getKLargest(arr, 4));
System.out.println(getKLargest(arr, 5));
System.out.println(getKLargest(arr, 6));
System.out.println(getKLargest(arr, 7));
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
public static int getKLargest(int[] arr, int k){
int[] heap = new int[k];
//put all elements in new array of size k
for(int i=0;i<k;i++){
heap[i] = arr[i];
//minHeapify(heap, 0, i+1);
}
//heapify the new array and start from last element so that our minHeapify func should work
for(int i=k-1;i>=0;i--){
//System.out.println("base heapify = "+heap[i]);
minHeapify(heap, i, k);
}
//System.out.println(Arrays.toString(heap));
//System.out.println("========================");
//make use of remaining elements in arr to check for kth largest
for(int i=k;i<arr.length;i++){
if(arr[i]>heap[0]){
heap[0] = arr[i];
minHeapify(heap, 0, k);
}
}
return heap[0];
}
public static void minHeapify(int[] heap, int start, int k){
//System.out.println(Arrays.toString(heap));
//get the left and right child index so that when we access the array it doesnt go out of bounds
//then check which child is smaller
//then compare smaller child to root and swap if smaller child < root
int leftChildIndex = (2*start)+1;
int rightChildIndex = (2*start)+2;
int minChildIndex=-1;
if(leftChildIndex<k && rightChildIndex<k){
minChildIndex = heap[leftChildIndex]<heap[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
else if(leftChildIndex<k){
minChildIndex = leftChildIndex;
}
else if(leftChildIndex<k){
minChildIndex = rightChildIndex;
}
//System.out.println("start = "+start+" left = "+leftChildIndex+" right = "+rightChildIndex+" minChild = "+minChildIndex);
if(minChildIndex!=-1){
if(heap[minChildIndex]<heap[start]){
swap(heap, start, minChildIndex);
minHeapify(heap, minChildIndex, k);
}
else if(heap[minChildIndex]<heap[start]){
swap(heap, start, rightChildIndex);
minHeapify(heap, rightChildIndex, k);
}
}
}
public static void swap(int[] arr, int firstElemIndex, int secondElemIndex){
int temp = arr[firstElemIndex];
arr[firstElemIndex] = arr[secondElemIndex];
arr[secondElemIndex] = temp;
}
}
Comments
Post a Comment