整體架構流程

大頂推：是構建一個完整的二叉樹
大頂推：即父節點的值大于左右子樹的值。

循環構建大頂推
在給定的數組，既可以明確樹的高度。
在循環的時候，構建樹的高度從lgn至0。即從堆低往堆頂構建。
構建過程中：如果左右子樹大于父節點，則交互數據后，在調整被交換的節點使其滿足大頂推。

提取大頂堆獲取排序值
從數組長度(i = a.length-1)至0循環：

1. 交換0和i的值（即大頂堆的跟節點，即最大值）。完成升序排序最大值在數組末尾。
2. 因將i的值替換到0的值位置，需要重新調整大頂堆。且將數組的長度限制小于i。

技術細節

package study.algorithm.sort;import java.util.Arrays;/*** 堆排序，是先構建一個完整的二叉樹*/
public class HeapSort {public static void main(String... args){int[] arr = {12, 11, 13, 5, 6, 7};System.out.println("排序前："+ Arrays.toString(arr));sort(arr);System.out.println("排序后："+ Arrays.toString(arr));}public static void sort(int[] arr) {builderMaxHeap(arr);// 逐個提取堆頂元素（最大值）并調整堆// 大頂堆的，最大值的索引是0。for (int i = arr.length - 1; i > 0; i--) {// 將當前堆頂元素（最大值）與末尾元素交換(即i)// 交換完成之后， 大于等于i的索引不參(i至arr.length)與后續大頂堆調整。int tmp = arr[0];arr[0] = arr[i];arr[i] = tmp;//調整剩余元素為最大堆，將最大值放在索引為0的位置。//指定需要調整的數組長度 i,從0索引位置開始調整大頂對。//因上一步，將未尾值換到了索引為0的位置，而索引0的左右子樹的值是剩余的最大值。maxHeap(arr,i,0);}}/*** 構建大頂推，即父節點的值，大于左右子樹的值*/public static void builderMaxHeap(int[] arr) {int n = arr.length;for (int i = n / 2; i >= 0; i--) {maxHeap(arr, n, i);}}/*** 構建大頂推，即父節點的值，大于左右子樹的值** @param arr 數組* @param n   需要調整整個數組的長度* @param i   父節點索引位置*/public static void maxHeap(int[] arr, int n, int i) {//最大值索引默認為i，i的左右子樹在數組中索引的位置int largest = i;int right = 2 * i + 1;int left = 2 * i + 2;//如果左子樹索引不越界(即存在左子樹)，且左子樹的值大于，最大值索引的值if (left < n && arr[left] > arr[largest]) {largest = left;}//如果右子樹索引不越界(即存在右子樹)，且右子樹的值大于，最大值索引的值if (right < n && arr[right] > arr[largest]) {largest = right;}//說明父節點的值，小于左右子樹的值//1. 調整堆的最大值位于父節點//2. 因左右子樹的值，存在修改則需要調整當前修改節點的堆，滿足大頂堆if (i != largest) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;maxHeap(arr, n, largest);}}
}

小結

構建大頂堆是從堆低往堆頂開始構建
每次獲取大頂堆最大的值，完成排序