##堆(优先级队列)的部分知识点##-平芜编程栈

一、堆的基本概念

堆本质上是一种特殊结构、特殊要求的二叉树，其主要用途是作为带有优先级的队列。

堆是一个完全二叉树，同时满足以下两个要求：

任意一个父节点的值，都大于两个子节点，整个树的根节点就是整体最大值（大堆）。
任意一个父节点的值，都小于两个子节点，整个树的根节点就是整体最小值（小堆）。

面试常问角度：堆与普通二叉树的区别是什么？为什么堆必须用完全二叉树实现？

二、堆的存储方式

把整棵树层序遍历，其结果放入数组中，此时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 的实例化和实现

代码实现：

PriorityQueue<Integer> queue = new PriorityQueue<>(new IntComparator());

class IntComparator implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; // 降序 } } // 在 compare 中 O1-O2 --> 返回升序，小的值先出去 // O2-O1 --> 返回降序，大的值先出去 // O1=O2 --> 返回 0

易错点提示：当o1 - o2可能溢出时（如Integer.MAX_VALUE - (-1)），应使用Integer.compare(o1, o2)或o1.compareTo(o2)代替直接相减。

3. Comparable 的实例化和实现

代码实现：

PriorityQueue<Integer> queue = new PriorityQueue<>();

class MyInt implements Comparable<MyInt> { int value; public MyInt(int value) { this.value = value; } @Override public int compareTo(MyInt other) { return this.value - other.value; // 注意：这是升序，降序反着减 } }

面试常问角度：Comparable 和 Comparator 的核心区别是什么？什么时候用哪一个？