package shujujiegou.二叉树;

import java.util.Arrays;

public class BinaryHeap {

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

    array=new int[]{7,1,3,10,5,2,8,9,6};
    buildJust(array);
    System.out.println(Arrays.toString(array));
}



/**
 * 上沉操作
 * @param array  待调整的堆
 */
private static void updateJust(int[] array) {
    int chilIndex=array.length-1;
    int parentIndex=(chilIndex-1)/2;

    //将temp保存插入叶子节点，用于最后的赋值
    int temp=array[chilIndex];

    //父节点大于子节点
    while (temp < array[parentIndex]  &&  chilIndex  >0){
        array[chilIndex]=array[parentIndex];
        chilIndex=parentIndex;
        parentIndex=(parentIndex-1)/2;
    }
    array[chilIndex]=temp;
}

/**
 * 构建堆
 * @param array 待调整的堆
 */
private static void buildJust(int[] array) {
    for (int i = (array.length-2)/2; i >=0 ; i--) {
        downAdjust(array,i,array.length);
    }
}

/**
 * 下沉策略
 * @param array 待调整的堆
 * @param parentIndex   要下沉的父节点
 * @param length 堆的有效大小
 */
private static void downAdjust(int[] array, int parentIndex, int length) {
    //temp 保存父节点 用于最后的赋值
    int temp=array[parentIndex];
    int childrenIndex = parentIndex*2 +1;

    while (childrenIndex <length){
        //如果有右孩子，且右孩子小于左孩子的值，则定位右孩子
        if (childrenIndex +1 <length &&  array[childrenIndex +1]  < array[childrenIndex]){
            childrenIndex++;
        }

        //如果父节点小于然后一个孩子的值，则直接跳出
        if (temp <array[childrenIndex]){
            break;
        }
        //无需真正交换，只需要单向赋值即可
        array[parentIndex]=array[childrenIndex];
        parentIndex=childrenIndex;
        childrenIndex =2*childrenIndex +1;
    }
    array[parentIndex] =temp;
}

}