树、二叉树的简单介绍
可以用数组表示一颗二叉树（数组下标从0开始）
左子节点下标是 2n+1 (n是父节点下标)
右子节点下标是 2n+2 (n是父节点下标)
父节点下标是 n/2-1 （n是左子节点或者右子节点下标）
堆的概念二叉堆是完全二叉树或者是近似完全二叉树
二叉堆满足两个特性：
父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值
每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）
任意节点的值都大于其子节点的值————大顶堆，堆的最大值在根节点。
任意节点的值都小于其子节点的值————小顶堆，堆的最小值在根节点。
第一步：堆化
反向调整使得每个子树都是大顶堆或者小顶堆
从n/2-1个元素开始向下修复，将每个节点修复为大（小）顶堆，修复完成后，数组具有大（小）顶堆的性质
举个例子：
初始给定数组为[2,7,26,25,19,17]
它所形成的二叉堆是
堆化以后变成大顶堆
数组变为[26,25,17,7,19,2]
第二步：调整
不停地把堆顶和未处理数组的最后一个元素交换，把堆顶也就是较大元素放到数组末端，每交换一次都要进行调整，维持二叉堆结构。
代码实现 法一：采用递归方式进行调整操作 public static void main(String[] args) { int[] arr = {2,5,6,21,6,4,2,6,2}; heapSort(arr); for (int i : arr) { System.out.print(i+" "); } } private static void heapSort(int[] arr){ mikeMaxHeap(arr); //1.先进行堆化 for(int x = arr.length-1;x>=0;x--){ //2.再进行调整 swap(arr,0,x); //把堆顶(0号元素)和最后一个元素对调 maxHeapFixDown(arr,0,x); //缩小堆的范围，对堆顶元素进行向下调整 } } private static void mikeMaxHeap(int[] arr) { int n = arr.length; for (int i = (n - 1 - 1) / 2; i >= 0; i--) { //从「第一个非叶子节点」开始向前调整，叶子节点没必要调整 maxHeapFixDown(arr, i, n); } } private static void maxHeapFixDown(int[] arr, int i, int size) { // 1.找到左右孩子 int left = 2 * i + 1; int right = 2 * i + 2; // 2.让max指向了左右孩子中较大的那个 if (left >= size) //左孩子已经越界，i就是叶子节点 return; int max = left; //先默认左右孩子中较大的那个是左孩子，简化代码 if (right >= size) //右孩子越界，孩子中较大的就是左孩子 max = left; else { //左右孩子都没越界，max指向较大的那个 if (arr[right] > arr[left]) max = right; } // 3.交换孩子节点和父亲节点 if(arr[i]>=arr[max]) // 如果arr[i]比两个孩子都要大，不用调整 return; swap(arr,i,max); //否则，找到两个孩子中较大的，和i交换 // 4.大孩子那个位置的值发生了变化，i变更为大孩子那个位置，递归调整 maxHeapFixDown(arr, max, size); } private static void swap(int[] arr, int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } 法二：采用循环方式进行调整操作只需要修改maxHeapFixDown方法
public static void main(String[] args) { int[] arr = {2,5,6,21,6,4,2,6,2}; heapSort(arr); for (int i : arr) { System.out.print(i+" "); } } private static void heapSort(int[] arr) { mikeMaxHeap(arr); //1.先进行堆化 for (int x = arr.length - 1; x >= 0; x--) { //2.再进行调整 swap(arr, 0, x); //把堆顶(0号元素)和最后一个元素对调 maxHeapFixDown(arr, 0, x); //缩小堆的范围，对堆顶元素进行向下调整 } } private static void mikeMaxHeap(int[] arr) { int n = arr.length ; //从「第一个非叶子节点」开始向前调整，叶子节点没必要调整 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { maxHeapFixDown(arr, i, n); } } private static void maxHeapFixDown(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { //如果存在右节点，则largest等于左右节点中较大者的下标 //如果不存在右节点，则largest等于左节点的下标 //一条语句同时满足两个条件，选出子节点中的较大者给largest int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; //选出子节点和父节点中的较大者 largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); //交换 index = largest; //进入下一次循环（下沉），重新计算index和left left = index * 2 + 1; } } private static void swap(int[] arr, int a, int b) { int tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } 时间复杂度分析第一步：建立大根堆的过程。