Heap Sort(max heap)

 public class HeapSortNew {

    public static void main(String[] args) {

        int[] arr = {4,1,7,2,3,8,10};

        int n= arr.length;

        for(int i=n/2-1;i>=0;i--){

            heapify(arr,n,i);

        }

        System.out.println(Arrays.toString(arr));

        for(int i=n-1;i>=0;i--){

            swap(arr,i,0);

            heapify(arr,i,0);

        }

        System.out.println(Arrays.toString(arr));

    }

    static void heapify(int[] arr, int n, int i){

        int l = 2*i+1;

        int r = 2*i+2;

        int largest = i;

        if(l<n){

            if(arr[l]>arr[largest]){

                largest = l;

            }

        }

        if(r<n){

            if(arr[r]>arr[largest]){

                largest = r;

            }

        }

        //if value get updated

        if(largest!=i){

            swap(arr,i,largest);

            heapify(arr,n,largest);

        }

    }

    static void swap(int[] arr, int i, int j){

        int temp = arr[i];

        arr[i]  =arr[j];

        arr[j]=temp;

    }

}

output:

[10, 3, 8, 2, 1, 4, 7]

[1, 2, 3, 4, 7, 8, 10]he

Find kth largest element in array in java using MaxHeap

 public class FIndKthLargestEmement {

    public static void main(String[] args) {

        int[] arr = {4,1,7,2,3,8,10};

        int n= arr.length;

        for(int i=n/2-1;i>=0;i--){

            heapify(arr,n,i);

        }

        System.out.println(Arrays.toString(arr));

        int k = 2;

//run the loop k times from last index , move root element to ith and heapify the array to maintain maxheap 

        for(int i=n-1;i>=n-k;i--){

            swap(arr,i,0);

            heapify(arr,i,0); //i due to don't like to incluede already sorted element

        }

        System.out.println(Arrays.toString(arr));

        System.out.println(arr[n-k]);

    }

    static void heapify(int[] arr, int n, int i){

        int l = 2*i+1;

        int r = 2*i+2;

        int largest = i;

        if(l<n){

            if(arr[l]>arr[largest]){

                largest = l;

            }

        }

        if(r<n){

            if(arr[r]>arr[largest]){

                largest = r;

            }

        }

        //if value get updated

        if(largest!=i){

            swap(arr,i,largest);

            heapify(arr,n,largest);

        }

    }

    static void swap(int[] arr, int i, int j){

        int temp = arr[i];

        arr[i]  =arr[j];

        arr[j]=temp;

    }

}

output:

[10, 3, 8, 2, 1, 4, 7]

[7, 3, 4, 2, 1, 8, 10]

8

Convert Min Heap into Max Heap

public class ConvertMinHeapToMaxheap {

    public static void main(String[] args) {

        ConvertMinHeapToMaxheap convertMinHeapToMaxheap = new ConvertMinHeapToMaxheap();

        int arr[]  ={3 ,5 ,9 ,6, 8, 20, 10, 12, 18, 9};

        for(int i = arr.length/2-1;i>=0;i--){

            convertMinHeapToMaxheap.heapify(arr,arr.length,i);

        }

        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 largest = i;

        if(l<n){

            if(arr[l]>arr[largest]){

                largest = l;

            }

        }

        if(r<n){

            if(arr[r]>arr[largest]){

                largest = r;

            }

        }

        if(largest!=i){

            int temp = arr[largest];

            arr[largest] = arr[i];

            arr[i] = temp;

            heapify(arr,n,largest);

        }

    }

}

output: [20, 18, 10, 12, 9, 9, 3, 5, 6, 8]