Sunday, 12 July 2020

Find kth min element in array in java using MinHeap

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]

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...