二叉堆的构建以及添加/删除实现

二叉堆的学习记录，实现的过程以及源码

每个根节点都大于或等于子节点的完全二叉树称为大顶锥，每个根节点都小于或等于子节点的完全二叉树称为小顶锥，大顶锥的锥顶就是整个树的最大值，小顶锥则是最小值，由于是完全二叉树，所以底层使用的物理数据结构为数组实现。

• 从末尾添加，二叉堆要使用上浮操作来完成自调节
• 从锥顶删除，将最末尾元素替换锥顶，然后开始下沉操作完成自调节
• 构建二叉锥，则是使用从最大的非子叶节点依次下沉完成自调节

上浮 ： 将元素与其父节点比较，若小于，则保存替换。到索引值小于0或者大于等于父节点的时候停止，再使用保存的值替换当前子节点即可。其中，获取父节点的索引和子节点的关系

int parentIndex = (childIndex-1)/2

下沉 ： 将元素与左右子节点中较小的进行比较，若大于，则保存替换，到索引值大于树长度-1或者不大于较小节点结束，然后替换父节点即可。其中父节点和子节点的关系是：

int childIndex = 2 * parentIndex + 1;

构建heap的非子叶节点的最大索引值和树的长度关系为：

int maxIndex = (arr.length -2 )/2;

源码如下

/**
 * @author hj
 * 2019-07-17 22:44
 * 关于二叉堆的测试类
 */
public class BinaryTreeHeapTest {


    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr1 = {0, 1, 2, 3, 5, 6, 7, 8, 9, 10};
        buildHeap(arr);
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 上浮调整
     *
     * @param arr 二叉堆
     */
    public static void upAdjust(int[] arr) {
        int lastIndex = arr.length - 1;
        int parentIndex = (lastIndex - 1) / 2;
        int tmp = arr[lastIndex];
        while (arr[parentIndex] > tmp && lastIndex > 0) {
            //这里只是单纯的赋值即可，在最后上浮结束完成交换
            arr[lastIndex] = arr[parentIndex];

            //获取下一轮的索引
            lastIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[lastIndex] = tmp;
    }

    /**
     * 下沉调整
     *
     * @param arr         要调整的堆
     * @param parentIndex 下沉的父节点的索引
     */
    public static void downAdjust(int[] arr, int parentIndex) {
        int length = arr.length;
        int tmp = arr[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {

            //获取左右节点中最小值索引
            if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }

            //小于左右节点中最小值则退出
            if (tmp <= arr[childIndex]) {
                break;
            }

            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;

        }
        //下沉结束
        arr[parentIndex] = tmp;
    }

    /**
     * 构建二叉堆
     *
     * @param arr 带构建的二叉树
     */
    public static void buildHeap(int[] arr) {
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i);
        }
    }
}

添加和删除逻辑直接在上浮和下沉逻辑之前简单构建二叉堆数组即可，简单就不记录了。