堆：

    1、完全二叉树

    2、所有父节点 大于子节点

    基础公式：
    1、定位parent = （i - 1） /2
    2、定位左侧节点 c1 = 2i +1
    3、定位右侧节点 c2 = 2i +2

    image.png

    我们从 最开始的节点进行的heapify ,只能对单个完全二叉树节点进行堆调整 ，并不能对整个二叉树进行全面覆盖
    /解决方案：从最底层的节点，倒着做heapify 就ok了/
    �
    观察一下特点：最后一个节点，然后针对 3 -> 2 -> 1 进行heapify
    最后一个节点的parent节点 就是我们开始进行倒着做heapify的开始节点

    image.png

    排序，最后一个节点 与 第一个节点互换，最大的值，砍掉也就是不进行堆重构
    image.png

    1、将数据 堆化后
    2、最后一个节点 与 第一个节点互换，最大的值，跑到了节点最后方（鉴定了顺序排序的结构）
    3、重新 堆重构 heapify是从上至下的 ，每次砍掉的 最大值不进行堆的重构

    1、堆重构(heapify) 递归
    2、堆倒叙 heapify 创建完整堆结构（完整二叉树）for
    3、首位互换，砍掉最后节点，重新堆重构 for

    1. public class TestMain {
    2.     public static void main(String[] args) {
    3.         //结果： 10，5，3，4，1，2
    4.         // int tree[] = {4,10,3,5,1,2};
    5.         // int n = tree.length;
    6.         // heapify(tree,n,0);
    7.         /*现在代码不够完善，因为我们从 最开始的节点进行的heapify ,只能对单个完全二叉树节点进行堆调整 ，并不能对整个二叉树进行全面覆盖*/
    8.         /*解决方案：从最底层的节点，倒着做heapify 就ok了*/
    9.         int tree[] = {4,10,3,5,1,2};
    10.         int n = tree.length;
    11.         //创建堆
    12.         // heapify(tree,n,0);
    13.         // buildHeap(tree,n);
    15.         //堆的首个节点是最大的，那么 我们将位置 与 最后一个互换之后，剪出来，重新构建堆，然后重复执行
    16.         heapSort(tree,n);
    17.         Arrays.stream(tree).forEach(System.out::println);
    18.     }
    20.     public static void heapSort(int tree[],int n){
    21.         //创建堆
    22.         buildHeap(tree,n);
    24.         for (int i = n - 1; i >=0 ; i--) {
    25.             //最后一个节点 与 第一个节点更换，最大的值，跑到了节点最后方
    26.             swap(tree,i,0);
    27.             //因为heapify是从上至下的，并且i-- 所以，第一次是 最后一个节点 第二次是倒数两个节点 ，不进行堆的重构
    28.             heapify(tree,i,0);
    29.         }
    30.     }
    32.     /**
    33.      * 创建完整的 【堆】
    34.      * 树从最后一个节点开始倒叙做 heapify
    35.      * @param tree  数组
    36.      * @param n     数组长度
    37.      */
    38.     public static void buildHeap(int tree[],int n){
    39.         //节点的索引位置 n - 1.因为parent结果 就是索引位置
    40.         int last_node =  n - 1;
    42.         int parent = (last_node - 1) / 2;
    44.         for (int i = parent; i >= 0  ; i--) {
    45.             heapify(tree,n,i);
    46.         }
    47.     }
    49.     /**
    50.      *
    51.      * 堆重构，顺序是从上至下
    52.      * @param tree 数组
    53.      * @param n    数组长度，防止越界
    54.      * @param i    开始堆重构的父节点
    55.      */
    56.     public static void heapify(int tree[],int n , int i){
    57.         if(i >= n){
    58.             return;
    59.         }
    61.         //获取两个节点 ;左侧节点 c1 = 2i +1
    62.         int c1 = 2 * i + 1;
    63.         int c2 = 2 * i + 2;
    64.         //假定 i是最大值
    65.         int max = i;
    67.         // 判断是否越界，堆节点进行重构
    69.         if(c1 < n && tree[c1] > tree[max]){
    70.             //节点位置
    71.             max = c1;
    72.         }
    74.         if(c2 < n && tree[c2] > tree[max]){
    75.             max = c2;
    76.         }
    78.         //如果max 不是最初假定的i为最大值，那么代表 下方节点 大于当前节点
    79.         if(max != i){
    80.             //进行数据交换
    81.             swap(tree,max,i);
    82.             //递归 将树完全排序
    83.             heapify(tree,n,max);
    84.         }
    85.     }
    87.     /**
    88.      * 上沉下浮 数据替换
    89.      * @param tree 数组
    90.      * @param max  最大值
    91.      * @param i    需要交换的小值
    92.      */
    93.     private static void swap(int[] tree, int max, int i) {
    94.         //最大的值 临时存储
    95.         int temp = tree[max];
    96.         //数据上沉
    97.         tree[max] = tree[i];
    98.         //数据下浮
    99.         tree[i] = temp;
    100.     }
    101. }