本文共 2273 字，大约阅读时间需要 7 分钟。
二叉堆本质上一种完全二叉树，分为：最小堆和最大堆，二叉堆的根结点叫做堆顶
最大堆：最大堆的任何一个父节点的值都大于或等于他的左右节点的值，最大堆的堆顶是整个堆中最大元素 最小堆：最小堆的任何一个父节点的值都小于或等于他的左右节点的值，最小堆的堆顶是这个堆中最小元素 二叉堆的几种操作： 1、插入节点：插入位置是完全二叉树的最后一个位置；堆的插入操作是单一节点的“上浮”，平均交换次数都是堆高度的一半，所以时间复杂度是O(logn) 2、删除节点：删除的是处于堆顶的节点；堆的删除操作是单一节点的“下沉”，平均交换次数都是堆高度的一半，所以时间复杂度是O(logn) 3、构建二叉堆：就是将一个完全无序的二叉树调整为二叉堆，本质上就是让所有非叶子结点依次“下沉”;时间复杂度是O(n)/** * 二叉堆构建 */public class Adjust { /** * "上浮"调整 * * @param arr */ public static void upAdjust(int[] arr) { if (arr == null) { return; } int childIndex = arr.length - 1; int parentIndex = (childIndex - 1) / 2; //保存插入的叶子结点的值，用于最后的赋值 int temp = arr[childIndex]; while (childIndex > 0 && temp < arr[parentIndex]) { //无须真正交换，单向赋值即可 arr[childIndex] = arr[parentIndex]; childIndex = parentIndex; parentIndex = (parentIndex - 1) / 2; } arr[childIndex] = temp; } /** * "下沉"调整 * * @param arr 待调整值 * @param parentIndex 待下沉的父节点 * @param length 堆的有效大小 */ public static void downAdjust(int[] arr, int parentIndex, int length) { int temp = arr[parentIndex]; int childIndex = parentIndex * 2 + 1; while (childIndex < length) { //如果有右孩子，且右孩子小于左孩子则定位到右孩子 if (childIndex + 1 < length && arr[childIndex + 1] < arr[childIndex]) { childIndex++; } //如果父节点小于任何一个孩子的值，直接退出 if (temp < arr[childIndex]) { break; } //无须交换，单向赋值即可 arr[parentIndex] = arr[childIndex]; parentIndex = childIndex; childIndex = 2 * childIndex + 1; } arr[parentIndex] = temp; } /** * 构建堆 * * @param arr */ public static void buildHeap(int[] arr) { //从最后一个非叶子节点开始，依次做下沉操作 for (int i = (arr.length - 2) / 2; i >= 0; i--) { downAdjust(arr, i, arr.length); } } public static void main(String[] args) { int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0}; upAdjust(arr); System.out.println(Arrays.toString(arr)); arr = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6}; buildHeap(arr); System.out.println(Arrays.toString(arr)); }}
转载地址：http://bqsvi.baihongyu.com/