##堆(优先级队列)的部分知识点##

一、堆的基本概念堆本质上是一种特殊结构、特殊要求的二叉树其主要用途是作为带有优先级的队列。堆是一个完全二叉树同时满足以下两个要求任意一个父节点的值都大于两个子节点整个树的根节点就是整体最大值大堆。任意一个父节点的值都小于两个子节点整个树的根节点就是整体最小值小堆。面试常问角度堆与普通二叉树的区别是什么为什么堆必须用完全二叉树实现二、堆的存储方式把整棵树层序遍历其结果放入数组中此时arr[0]就是根节点。已知父节点的下标是i已知子节点下标为i左子树下标为2i 1右子树下标为2i 2。父节点下标为(i - 1) / 2。易错点提示下标推导时注意区分「已知父节点求子节点」和「已知子节点求父节点」两组公式不要混淆。三、堆的创建和实现1. 向下调整适用场景整棵树除了根节点以外都已经符合堆的要求只差根节点自己不符合要求。代码实现// 向下调整 public static void shiftDown(int[] arr, int size, int subRoot) { int parent subRoot; int child parent * 2 1; while (child size) { // 选出左右孩子中较大的一个 if (child 1 size arr[child] arr[child 1]) { child child 1; } // 如果父节点已经大于等于较大的孩子则调整结束 if (arr[parent] arr[child]) { break; } // 否则交换父节点与较大的孩子 int tmp arr[child]; arr[child] arr[parent]; arr[parent] tmp; // 继续向下调整 parent child; child parent * 2 1; } }时间复杂度O(log n)空间复杂度O(1)。易错点提示原代码中parent child * 2 1; child parent;的更新顺序写反了会导致死循环或越界。正确写法是先更新parent child再计算新的child parent * 2 1。2. 向上调整适用场景只有当前节点不符合堆的要求。代码实现// 向上调整 public static void shiftUp(int[] arr, int child) { int parent (child - 1) / 2; while (child 0) { // 如果当前节点大于父节点则交换 if (arr[child] arr[parent]) { int tmp arr[child]; arr[child] arr[parent]; arr[parent] tmp; } else { // 已经满足堆的性质提前结束 break; } // 继续向上调整 child parent; parent (child - 1) / 2; } }时间复杂度O(log n)空间复杂度O(1)。理由说明向上调整每次只沿一条从叶子到根的路径进行路径长度不超过树的高度log n因此时间复杂度为O(log n)整个过程只使用常数个临时变量因此空间复杂度为O(1)。易错点提示原代码中if (arr[child] arr[parent])的比较方向写反了这是小堆的写法且交换后缺少else break分支会导致不必要的继续循环。向上调整的终止条件是child 0或当前节点已满足堆的性质。3. 创建堆代码思路基于向下调整实现。找到最后一个非叶子节点(size - 1 - 1) / 2从该节点开始向下调整调整完毕之后都往前走一步。代码实现// 创建堆 public static void createHeap(int[] arr, int size) { // 从最后一个非叶子节点开始向前逐个向下调整 for (int root (size - 1 - 1) / 2; root 0; root--) { shiftDown(arr, size, root); } }时间复杂度O(n)空间复杂度O(1)迭代。易错点提示原代码中for (int root size - 1 - 1; root 0; root--)有两个错误一是循环条件应为root 0否则下标为 0 的根节点不会被调整二是方法名creatHeap拼写错误应为createHeap。4. 插入元素入队列代码思路新元素进行尾插从新元素开始向上调整。代码实现public static int add(int[] arr, int size, int val) { if (size arr.length) { throw new RuntimeException(堆已满无法插入); } arr[size] val; size; shiftUp(arr, size - 1); return size; }时间复杂度O(log n)空间复杂度O(1)迭代。面试常问角度为什么插入操作的时间复杂度是 O(log n)如果数组扩容空间复杂度会变成多少5. 删除堆顶元素出队列代码思路直接用数组的最后一个元素代替根节点的位置同时size--然后从根节点开始向下调整。代码实现// 删除堆顶元素 public static int remove(int[] arr, int size) { if (size 0) { throw new RuntimeException(堆为空无法删除); } int top arr[0]; // 用最后一个元素代替堆顶元素 arr[0] arr[size - 1]; size--; // 进行向下调整 shiftDown(arr, size, 0); return top; }时间复杂度O(log n)空间复杂度O(1)迭代。易错点提示原代码中remove方法返回的是size删除后的元素个数而不是被删除的堆顶元素值这在语义上是错误的。正确做法是先用临时变量保存arr[0]调整完成后返回该值。四、Comparable 和 Comparator 的实现和区别1. 回调函数不需要我们自己主动调用而是交给别人让他们在合适的时机进行调用。面试常问角度回调函数在 Java 集合框架中还有哪些应用场景2. Comparator 的实例化和实现代码实现PriorityQueueInteger queue new PriorityQueue(new IntComparator());class IntComparator implements ComparatorInteger { Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 降序 } } // 在 compare 中 O1-O2 -- 返回升序小的值先出去 // O2-O1 -- 返回降序大的值先出去 // O1O2 -- 返回 0易错点提示当o1 - o2可能溢出时如Integer.MAX_VALUE - (-1)应使用Integer.compare(o1, o2)或o1.compareTo(o2)代替直接相减。3. Comparable 的实例化和实现代码实现PriorityQueueInteger queue new PriorityQueue();class MyInt implements ComparableMyInt { int value; public MyInt(int value) { this.value value; } Override public int compareTo(MyInt other) { return this.value - other.value; // 注意这是升序降序反着减 } }面试常问角度Comparable 和 Comparator 的核心区别是什么什么时候用哪一个4. 两者的区别Comparable 中的compareTo只能实现唯一的一种比较规则Comparator 中的compare可适应多种比较规则可以定义多种比较器。5. 选择建议如果只有一套比较规则用Comparable如果有多套比较规则用Comparator。面试常问角度为什么说 Comparator 比 Comparable 更灵活在排序算法中如何动态切换比较器