public class findKthsmallestElement {
public static void main(String[] args) {
int[] arr = {4,1,7,2,3,8,10};
findKthsmallestElement findKthsmallestElement = new findKthsmallestElement();
findKthsmallestElement.findKth(arr,3);
}
void findKth(int[] arr,int kth){
if(kth<=0 || kth>arr.length){
System.out.println("no element found");
return;
}
for(int i = (arr.length/2)-1;i>=0;i--){
heapify(arr,arr.length,i);
}
System.out.println(Arrays.toString(arr));
int length = arr.length;
//execute loop k times from end index, move root element to ith element and heapify again to maintain min heap
for(int i= length-1;i>=length-kth ;i--){
swap(arr,i,0);
heapify(arr,i,0);
}
System.out.println(+kth+" kth:"+arr[arr.length-kth]);
System.out.println(Arrays.toString(arr));
}
void heapify(int[] arr, int n,int i){
int l = 2*i+1;
int r = 2*i+2;
int smallest = i;
if(l<n){
if(arr[l]<arr[smallest]){
smallest = l;
}
}
if(r<n){
if(arr[r]<arr[smallest]){
smallest = r;
}
}
if(smallest!=i){
swap(arr,i,smallest);
heapify(arr,n,smallest);
}
}
void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
output:
[1, 2, 7, 4, 3, 8, 10]
3 kth:3
[4, 8, 7, 10, 3, 2, 1]
