排序2堆排序算法

1.完全二叉树的概念

除了最后一层之外的其它每一层都被完全填充，并且所有的节点都保证向左对齐。

2.堆的结构

首先，堆结构就是一棵完全二叉树；

堆分为大根堆（任何一棵子树的最大值都在头部）；小根堆（任何一棵子树的最小值都在头部）；

3.堆排序的思路

    3.1 将数组变为堆的结构（大根堆）

    3.2 将堆顶数据和最后一个数据交换，输出新的最后一个数据（也就是最大值），调整剩余的数据变成大根堆

4.代码实现

    4.1 将数组变为堆结构

        思路：假设要操作的数据（就是把数据插入到堆里面）下标是i，将它和它的父节点（(i-1)/2）比较,如果比他的父节点大，就交换；再接着一直往上比较，一直到它比父节点小了。

1.构造堆结构(从下往上走)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;} }

    4.2 在3.2中交换以后，重新调整堆结构

         思路：确定要调整结构的数据坐标，比较他的左右孩子，把其中较大的和它比较，孩子大就交换，在新位置重新调整堆结构；否则的话，不用调整，直接跳出。

//2.重新调整堆结构（堆顶数据变换之后，要重新调整堆结构）public static void heapify(int[] arr,int index,int heapSize) {int left=2*index+1;while(left

4.3 总流程