hymn

二叉堆操作：

1. 插入节点
2. 删除节点
3. 构建二叉堆

以最小堆为例：

（一）插入节点时，插入位置是完全二叉树的最后一个位置，通过“上浮”的操作实现平衡

（二）删除节点与插入节点刚好相反，将最后一个位置的节点补到删除位置，然后通过“下沉”的操作实现平衡。

（三）构建二叉树，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。

package tree;

import java.util.Arrays;

/**
 * @author: daixyhymn
 * @description: 二叉堆
 * @date: 2020/11/3 16:50
 */
public class TreeHeap {

  /**
   * "上浮"
   * @param array
   */
  public static void upAdjust(int[] array){
    int childIndex = array.length - 1;
    int parentIndex = (childIndex - 1) / 2;
    // temp 保存插入的叶子节点，用于最后的赋值
    int temp = array[childIndex];
    while (childIndex > 0 && temp < array[parentIndex]){
      // 无需正真的交换，单项赋值就好
      array[childIndex] = array[parentIndex];
      childIndex = parentIndex;
      parentIndex = (childIndex - 1) / 2;
    }
    array[childIndex] = temp;
  }

  /**
   * “下沉”
   * @param array
   * @param parentIndex
   * @param length
   */
  public static void downAdjust(int[] array, int parentIndex, int length){
    // temp 保存父节点值，用于最后的赋值
    int temp = array[parentIndex];
    int childIndex = 2 * parentIndex + 1;
    while (childIndex < length){
      // 如果有有孩子并且有孩子小于左孩子，定位到右孩子
      if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]){
        childIndex++;
      }
      // 如果父节点小于任何一个子节点，直接跳出
      if (temp < array[childIndex]){
        break;
      }
      // 无需正真的交换，单项赋值就好
      array[parentIndex] = array[childIndex];
      parentIndex = childIndex;
      childIndex = parentIndex * 2 + 1;
    }
    array[parentIndex] = temp;
  }

  /**
   * 构建二叉堆
   * @param array
   */
  public static void buildHeap(int[] array){
    // 从最后一个非叶子节点开始，一次做“下沉”
    for (int i = (array.length - 2) / 2; i >= 0; i--){
      downAdjust(array, i, array.length);
    }
  }

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

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