一、堆结构（重要）：

1、堆结构就是用数组实现的完全二叉树结构

2、完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3、完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4、堆结构的heapinsert与heapify操作

5、堆结构的增大和减少

6、优先级队列结构，就是堆结构

二、变成堆结构的两个重要的过程

1、heapInsert过程

    //index表示当前节点，或者是插入的结点位置
    public static void heapInsert(int[] arr,int index){
        //如果子节点的数大于父节点的数，则进行交换位置，变成大根堆
        while(arr[index]>arr[(index-1)/2]){
            //交换位置
            swap(arr,index,(index-1)/2);
            //将当前节点变为index，继续比较
            index = (index-1)/2;
        }
    }

2、heapify过程

    public static void heapIfy(int[] arr,int index,int heapSize){
        //左孩子的下标
        int left = index * 2 +1;

        while(left<heapSize){//当左孩子的结点下标小于堆的最大空间，因为左孩子的下标小于右孩子，所以说明该结点有孩子
            //两个孩子中，谁的值大，把下标给largest,left+1表示右孩子的下标
            //left+1 < heapSize：表示有右孩子 arr[left+1] > arr[left]：表示右孩子的数大于左结点的数
            //成立的话，将父节点的下标给largest，不成立的话说明左孩子的数大，将左孩子的下标数给largest
            int largest = left+1 < heapSize && arr[left+1] > arr[left] ? left +1:left;

            //上面是比较两个子节点那个数大，接下来比较父节点的数和上面获取到的最大的数
            largest = arr[index] > arr[largest] ? index : largest;

            //如果此时的结点就是父节点，并不用交换，退出循环
            if(largest == index){
                break;
            }
            //否则，交换最大值的位置和父节点的位置，也就是将最大值的交换到父节点
            swap(arr,largest,index);
            //将当前父节点index变为largest
            index = largest;
            //将左孩子的下标变为当前父节点的左孩子下标
            left = index*2+1;
        }
    }

三、堆排序，HeapSort过程

public class code_HeapSort{
public static void heapSort(int arr[]){
//首先判断数组长度为0或者为1的时候，就不用进行堆排序
if(arr == null || arr.length<2){
return;
}
//经过上面的判断，可以进行heapInsert过程
for(int i=arr.length;i>=0;i--){
HeapIfy.heapIfy(arr,i,arr.length);
}
int heapSize = arr.length;
HeapIfy.swap(arr,0,heapSize);
while(heapSize > 0){
//判断，循环条件是此堆里面还有数
HeapIfy.heapIfy(arr,0,--heapSize);
}
}
}