public class Test2 {
    private  int[] array;
    private  int usedSize; // 当前堆中的有效元素个数
    Test2() {
        array = new int[10]; // 通过构造方法给数组分配空间
    }
    // 向上调整保证是小根堆：时间复杂度是O(log以2为底的N)---log2N
    public  void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (this.array[child] < this.array[parent]) {
                int tmp = this.array[child];
                this.array[child] = array[parent];
                this.array[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }
            else {
                break;
            }
        }
    }
    // 向堆中插入元素
    public  void offerHeap(int val) {
        if (this.usedSize >= this.array.length) {
            System.out.println("数组已满，插入失败！");
        }
        else {
            this.array[usedSize] = val;
            shiftUp(usedSize);  // 插入数据后进行向上调整确保为小堆
            ++usedSize;         // 堆中有效元素加一个
        }
    }
    // 向上调整建立小根堆，时间复杂度是O(n * log2N)
    public void createHeapUp() {
        int[] a = {4, 2, 7, 8, 5, 1, 0, 6};
        // 遍历a数组，将a数组中的元素一个一个的插入堆中
        for (int i = 0; i < a.length; i++) {
            offerHeap(a[i]);
        }
    }
    public static void main(String[] args) {
        Test2 test2 = new Test2();
        test2.createHeapUp();
    }
}

import java.util.Arrays;
// 向上调整建立小根堆
public class Main {
    public static void main(String[] args) {
        Main tmp = new Main();
        int[] array =  {4, 2, 7, 8, 5, 1, 0, 6};
        //int[] array = {4, 1, 3, 2, 0};
        tmp.createHeapUp2(array);
        System.out.println(Arrays.toString(array));
    }
    // 向上调整保证是小根堆：时间复杂度是O(log以2为底的N)---log2N
    public  void shiftUp(int[] array, int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (array[child] < array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }
            else {
                break;
            }
        }
    }
    // 建立小根堆的方法二：
    // 向上调整建立小根堆，时间复杂度是O(n * log2N)
    public  void createHeapUp2(int[] array) {
        for (int i = 1; i < array.length; ++i) {
            shiftUp(array, i); // 对数组的每一个元素进行向上调整
        }
    }
    // 我们向下调整来建堆时，要保证当前要调整的节点的左右子树都已经是堆后，才可以向下调整。
    // 向上调整来建立堆的时候，也是相似的，要保证要调整的节点前面已经是一个合法的堆才行——
    // 为了达到这个目的，我们在向上建堆的时候，就需要从数组的第二个元素开始（也可以理解为第二层的第一个节点）
}

import java.util.Arrays;
public class Test3 {
    public void createHeap(int[] arrays) {
        // 从倒数的第一个非叶子节点开始调节(调节他的左右子树），一直调节到根结点（根节点在数组中的下标为0）
        // 注意这里是usdSize - 1 - 1,因为父亲结点的下标 = (孩子结点的下标 - 1） / 2，
        // 我们是从倒数的第一个非叶子节点的子树开始调节的，而该子树的孩子结点坐标为arrays.length - 1
        for (int i = (arrays.length - 1 - 1) / 2; i >= 0 ; --i) {
            shiftDown(arrays, i); // 从下面的子树一直调到上面的子树
        }
    }
    /**
     * 向下调整——使得当前子树为小根堆
     * @param root 是每棵子树的根结点的下标
     * 向下调整的时间复杂度O(log2n)（最坏情况下就是树的高度）
     */
    public void shiftDown(int[] arrays, int root) {
        int parent = root; // 父亲结点的坐标
        int child = 2 * parent + 1; // 获取左孩子结点的坐标
        // 为什么不能child下标要小于usedSize,因为当前数组的最大下标就是usedSize - 1,如果大于或等于usedSize就越界了
        while (child < arrays.length) { // 每个子树在调整的时候，是按从上到下，当child的下标小于usedSize时候就结束
            // 这一步目的是找出孩子结点最小的那个值，然后在让该值和父亲结点比较（不过先要确定孩子结点存在）
            if (child + 1 < arrays.length - 1 && arrays[child] > arrays[child + 1]) {
                child = child + 1;
            }
            if (arrays[child] < arrays[parent]) {
                int tmp = arrays[child];
                arrays[child] = arrays[parent];
                arrays[parent] = tmp;
                parent = child; // 从上向下调整子树，更新父亲结点的下标
                child = 2 * parent + 1; // 更新左孩子孩子结点的下标
            }
            // 因为我们是从上向下调整子树，当我们在调整上面的子树时，下面的子树一定是调整好了的，如果上面都已经满足小根堆，下面也一定满足
            else {
                break; // 此时已经是小根堆了，不需要再次调整，直接退出循环接着调整下一个子树
            }
        }
    }
    public static void main(String[] args) {
        Test3 test3 = new Test3();
        int[] a = {4, 2, 7, 8, 5, 1, 0, 6};
        test3.createHeap(a);
        // 注意我们建立的小根堆没有储存在a数组中，而是储存在Test3类中的elem数组中
        System.out.println(Arrays.toString(a));
    }
}