如何构建最小堆？

方式1：上浮调整

/*** 上浮调整(小的上浮)*/
public static void smallUp1(int[] arr, int child) {int parent = (child - 1) / 2;while (0 < child && arr[child] < arr[parent]) { // 0 < child说明这个节点还是叶子arr[child] = arr[child] ^ arr[parent];arr[parent] = arr[child] ^ arr[parent];arr[child] = arr[child] ^ arr[parent];child = parent;                             // 父节点此时开始视为子节点parent = (child - 1) / 2;                   // 算父节点的父节点}
}
/*** 上浮调整(小的上浮)*/
public static void smallUp2(int[] arr, int child) {int parent = (child - 1) / 2;int baseVal = arr[child];                       // 把处理的数据取出来while (0 < child && baseVal < arr[parent]) {arr[child] = arr[parent];                   // 父节点值挪下来，父节点为baseVal备选位置child = parent;parent = (child - 1) / 2;}arr[child] = baseVal;                           // baseVal上浮不动了，所以落在当前子节点位置
}

方式2：下沉调整

/*** 下浮调整(大的下沉)** @param arr    待调整的堆* @param parent 要下沉的父节点* @param length 堆的有效大小*/
public static void bigDown1(int[] arr, int parent, int length) {int child = 2 * parent + 1;while (child < length) { // 范围内if (child + 1 < length && arr[child + 1] < arr[child]) { // 取出两个子节点值最小的那个child++;}if (arr[parent] <= arr[child]) {       // 父节点比他们都小，则符合预期终止循环break;}arr[child] = arr[child] ^ arr[parent];arr[parent] = arr[child] ^ arr[parent];arr[child] = arr[child] ^ arr[parent];parent = child;                         // 此时子节点视为父节点继续下一步处理child = 2 * child + 1;}
}
/*** 下浮调整(大的下沉)** @param arr    待调整的堆* @param parent 要下沉的父节点* @param length 堆的有效大小*/
public static void bigDown2(int[] arr, int parent, int length) {int baseVal = arr[parent];int child = 2 * parent + 1;while (child < length) {if (child + 1 < length && arr[child + 1] < arr[child]) {child++;}if (baseVal <= arr[child]) {break;}arr[parent] = arr[child]; // 子节点小，则子节点位置上移parent = child;child = 2 * child + 1;}arr[parent] = baseVal;        // baseVal下沉不动了，所以落在当前子节点位置
}

构建最小堆

int[] arr = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};System.out.println("原始数据：" + Arrays.toString(arr));
for (int i = arr.length - 1; i >= 0; i--) {smallUp1(arr, i);
}
System.out.println("上浮构建最小二叉堆：" + Arrays.toString(arr));int[] arr2 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = arr2.length - 1; i >= 0; i--) {smallUp1(arr2, i);
}
System.out.println("上浮构建最小二叉堆：" + Arrays.toString(arr2));int[] arr11 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = (arr11.length - 1) / 2; i >= 0; i--) {bigDown1(arr11, i, arr11.length);
}
System.out.println("下沉构建最小二叉堆：" + Arrays.toString(arr11));int[] arr22 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = (arr22.length - 1) / 2; i >= 0; i--) {bigDown2(arr22, i, arr22.length);
}
System.out.println("下沉构建最小二叉堆：" + Arrays.toString(arr22));原始数据：[1, 3, 2, 9, 5, 7, 8, 6, 10, 0]
上浮构建最小二叉堆：[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
上浮构建最小二叉堆：[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
下沉构建最小二叉堆：[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
下沉构建最小二叉堆：[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]