堆的结构可以分为大顶堆和小顶堆，是一个完全二叉树。
首先说明什么是完全二叉树：
若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。例如下图就不是一个完全二叉树，虽然1，2层均达到最大个数，但是第三层的节点应几种在左侧，即点7应该位于8的左子节点
其次说明什么是大顶堆和小顶堆：
每个结点的值都大于其左子节点和右子结点的值，称之为大顶堆；每个结点的值都小于其左子节点和右子结点的值，称之为小顶堆。下图即为大顶堆，下文的堆排序算法均以大顶堆为例。
堆排序思路：
首先将数组构造为一个大顶堆
将第一个元素与最后一个元素交换，即最后一个元素成为最大值
将新的数组构成大顶堆，再将第一个元素与最后一个元素交换，以此类推…
下面给一个具体案例
//对arr数组进行堆排序
int[] arr = new int[] {7,2,3,4,9,8,10};
在进行堆排序的时候我们先要考虑如何构建大顶堆,我们看下下面这个函数
public static void adjustHeap(int[] arr,int start,int end){
int temp = arr[start];//存储顶点值
// start * 2 + 1为左子节点 start * 2 + 2为右子节点
for (int i = start * 2 + 1; i <= end ; i = start * 2 + 1) {
if(i + 1 <= end && arr[i + 1] > arr[i]){//若右子节点值大于左子节点的值
i++;//指向右子节点
}
if(arr[i] > temp){
arr[start] = arr[i];
start = i;
}
}
arr[start] = temp;
}
首先说明这个函数是比较start节点与其左右子节点的最大值，若左右子节点大于arr[start]则进行替换，替换后需要分析被替换的子节点是否大于它的左右子节点（这里有点绕），若不需要替换则直接退出。那么如何借助这个函数构建大顶堆？我们看下实例：
// arr.length / 2 - 1为最右下脚的非叶子节点
for (int i = arr.length / 2 - 1; i >= 0; i--) {//从右至左从上至下！
adjustHeap(arr,i,arr.length - 1);
}
注意：遍历顺序为从右至左从下至上遍历所有非叶子节点
解释一下：
循环第一次对应图1，i为2，对3，8，10三个点进行处理，在8与10中选择10与3替换，替换结果为图2。
第二次对应图2，i为1，对2，4，9三个点进行处理,在4与9中选择9与2替换，替换结果为图3。
第三次对应图3，i为0，对7，9，10三个点进行处理,在9与10中选择10与7替换，需要注意的是替换完后，7下面还有子节点8，3需要再进行比较让8与7替换，到此该数组为大顶堆，如图4。结合第三次体会adjustHeap函数更佳
当数组变为大顶堆后，将第一个元素，即最大元素与最后一个元素交换，就成功将最大值移动到数组的最后一位。下面我们只需要将数组{3，9，8，4，2，7}调整成大顶堆依次后移第一位元素即可。需要注意的是此次调整只需要进行一次adjustHeap()函数即可，因为除了顶点3其他节点已经满足条件，所以只需要做上面循环的最后一步！
完整代码如下：
public static void main(String[] args) {
//对arr数组进行堆排序
int[] arr = new int[] {7,2,3,4,9,8,10};
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr,i,arr.length - 1);
}
for (int i = arr.length - 1; i > 0 ; i--) {
//交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,i - 1);
}
System.out.println(Arrays.toString(arr));
}
时间复杂度为O(nlog n)空间复杂度为O(1)
