堆是一棵圆满的二叉树，除了最后一层外，其他的每一层都是满的。

最大堆性质：表示每一个父节点的值都要比它的自己点的值要大，这里堆排序就是利用最大二叉堆的性质来进行排序的。

在进行堆排序之前，我们需要构建一颗完整的最大二叉堆，而构建最大二叉堆又需要利用到最大二叉堆的性质，所以我们需要先构建一个最大最大二叉堆的函数，代码如下：

/** * 保持最大堆的性质，父节点大于两个子节点 * @param arr * @param i */public static void max_heapify(int arr[], int i,int size) { //获取以i为根节点的堆的左子节点和右子节点 int left = 2 * i; int right = 2 * i + 1; //选出a[i] 和该节点的左右子节点的最大值，并将最大值跟a[i]出交换 int largest = i; if (left <= size && arr[i] < arr[left]) { largest = left; } if (right <= size && arr[largest] < arr[right]) { largest = right; } //交换两个位置 if (largest != i) { int tem = arr[i]; arr[i] = arr[largest]; arr[largest] = tem; //递归子节点的子节点 max_heapify(arr, largest,size); }}

在正式进行排序之前，我们需要构建一个完整的二叉堆，构建二叉堆的代码如下：

/** * 构建最大二叉堆 * @param arr * @param size */public static void build_max_heap(int[] arr, int size) { //第一次循环时i = n / 2 -1,因为下标从0开始 for (int i = (arr.length - 1) / 2; i >= 1; i--) { max_heapify(arr,i,size); }}

这样就是构建了完整的最大二叉堆，原理如下图：

构建完整的最大二叉堆的流程

通过如上的方式，我们已经构造了一颗最大二叉堆，那么在该二叉树中的的根节点肯定是整个堆中最大的值，将该节点跟整棵树中的最后一个节点交换，减少堆大小,这样保存到数组后面的数据就不会被交换(被堆元素数量)限制了，不断的渐少堆元素的数量，直到堆的大小从n-1到1为止；

代码如下：

public static void head_sort(int[] arr,int size) { //构建最大二叉堆 build_max_heap(arr, size); //循环二叉树交换二叉堆中的根节点和最后一个节点 for (int i = size; i >= 1; i--) { int tem = arr[0]; arr[0] = arr[i]; arr[i] = tem; //每次都减少二叉堆数量，构建i 为根节点的最大二叉堆 max_heapify(arr,0, i - 1); }}

这就是整个堆排序的的完整的三个方法。