用的是顺序存储二叉树，也就是数组实现的二叉树，遍历的时候按照的是二叉树的形式

在这里插入图片描述

代码实现

package tree;
import java.util.Arrays;
public class HeapSort { 
    public static void main(String []args){ 
        int [] arr = { 4, 6, 8, 5, 9,-1,-1,2,4,5,6,88};
        heapSort(arr);
    }
    //编写堆排序方法
    public static void heapSort(int arr []){ 
        System.out.println("堆排序");
        int temp = 0;
        //建堆(第一次整体是无序的，需要从下往上，从左往右开始建大顶堆)
        for (int i = arr.length / 2 -1; i >= 0 ; i--) { 
            adjustHeap(arr,i,arr.length);
        }
        //不断交换重构大顶堆（因为第一次重构的时候已经有序，交换后只是root节点无序，只需要把root节点的值放到他该去的位置即可，所以从顶点往下开始重构，然后循环）
        for (int j = arr.length -1; j > 0; j--) { 
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }
        System.out.println("数组："+ Arrays.toString(arr));
    }
    //将数组（二叉树），调整成大顶堆
    /** * 功能：{4, 6, 8, 5, 9} => i = 1 以6为非叶子节点的 子树 调整成大顶堆{4, 9, 8, 5, 6}（让6与两个孩子比较，比 6 大就交换）， * 然后继续调整传入i = 0，以4位节点的树调整成大顶堆（让4与两个孩子比较，比 4 大就交换） * @param arr 待调整的数组 * @param i 非叶子节点在数组中的索引 * @param length 对多少个元素进行调整（调整好的就不进行调整），length不断减少 */
    public static void adjustHeap(int arr [], int i, int length){ 
        int temp = arr[i]; //保存此非叶子节点
        //开始调整
        //说明k是i的左子节点
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) { 
            if (j+1 < length && arr[j] < arr[j+1]){ //说明左子节点小于右子节点
                j++; //j 指向右子节点
            }
            if (arr[j] > temp){ //如果子节点大于父节点
                arr[i] = arr[j];//把较大的值附给当前节点
                i = j; //！！！ i指向j，继续循环比较
            }else { 
                break;
            }
        }
        arr[i] = temp;
    }
}