package daweiguo.other;

/**
 * @Author DaWeiGuo
 * @Date 2022/3/19 21:04
 * @Desc:
 */
public class HeapSort {
    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] arr = new int[]{4,10,3,5,1,2};
        heapSort.heapSort(arr,arr.length);
        for(int a:arr){
            System.out.println(a);
        }
    }
    public void heapSort(int[] arr,int len){
        buildHeap(arr,len);
        for(int i=len-1;i>=0;i--){
            swap(0,i,arr);
            adjustHeap(arr,0,i);
        }
    }
    private void adjustHeap(int[] arr,int i,int len){
        if(i>=len) return;
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if(c1<len && arr[c1]>arr[max]){
            max = c1;
        }
        if(c2<len && arr[c2]>arr[max]){
            max = c2;
        }
        if(max!=i){
            swap(max,i,arr);
            adjustHeap(arr,max,len);
        }

    }
    private void buildHeap(int[] arr,int len){
        int lastNode = len - 1;
        int parentNode = (lastNode - 1)/2;
        for(int i=parentNode;i>=0;i--){
            adjustHeap(arr,i,len);
        }
    }
    private void swap(int x,int y,int[] arr){
        int t = arr[x];
        arr[x] = arr[y];
        arr[y] = t;
    }
}