堆的概念

1.堆分为大根堆（父节点最大）和小根堆（父节点最小）
2.堆是完全二叉树
3.完全二叉树是满二叉树或者上面的层全满，最底层所有的结点都连续集中在最左边的树

堆（完全二叉树）

堆排序的思路

1.将数组看成一颗完全二叉树，i的左节点为left = i * 2 + 1;右节点为left + 1；
2.插入节点算法heapInsert。将插入的节点与父节点比较，大于父节点则与父节点交换位置，重复此过程直到不大于父节点;
3.当有节点数值变小时，对该节点检查并排序，算法heapify。将该节点与其较大的子节点比较，小于子节点则交换位置，重复此过程直至不小于其子节点；

具体步骤

4.用heapInsert将数组排成大根堆；
5.将堆顶与数组最后一个数交换，将堆的大小减一（把最大数移到数组末尾，相当于最后一个位置已经排好了）；
6.用heapity方法将堆顶排序，重复步骤5,6；直到堆的大小等于1；

代码实现

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {1,2,3,2,5,6,9,1,2,3,4,5,8,2,3,6,5,4,1,8,9,7,55,22};
        heapsort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void heapsort(int[] arr) {
        if(arr == null || arr.length < 2)
            return;
        for(int i = 1; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapsize = arr.length;
        swap(arr, 0, --heapsize);
        while(heapsize > 0) {
            heapify(arr, 0 , heapsize);
            swap(arr, 0, --heapsize );
        }
    }
    
    public static void heapInsert(int[] arr, int i) {
        while(arr[i] >  arr[(i -1) / 2 ]) {
            swap(arr, i, (i -1) / 2);
            i = (i -1) / 2;
        }
    }
    
    public static void heapify(int[] arr, int idex, int size) {
        int left = idex * 2 + 1;
        while(left < size) {
            int largest = left ;
            if(left + 1 < size && arr[left] < arr[left + 1])
                largest = left + 1;
            if(arr[idex] >= arr[largest]) {
                break;
            }
            swap(arr, idex, largest);
            idex = largest;
            left = idex * 2 + 1;
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}