完全二叉树基础
完全二叉树
完全二叉树的定义
若一棵二叉树除最后一层外，其余层都是填满的，并且最后一层的节点从左至右依次连续排列，那么这样的二叉树被称为 “完全二叉树”。
特别地，如果最后一层也是填满的，那么这样的完全二叉树被称为 "完美二叉树"。
这颗二叉树是一棵完全二叉树：
而下面这棵树不是完全二叉树，因为最后一层的节点不是从左往右连续填充的：
完全二叉树的数组表示
首先，以一棵具有 12 个节点的完全二叉树为例。我们按照层序遍历的顺序，从 0 开始依次为每个节点编号。例如：
请你观察任意一组父节点及其子节点们，它们之间的编号存在什么数量关系？
也就是说，父节点的编号是怎么映射到左右子节点的编号的？某个节点的编号是怎么映射到父节点的编号的？
设某一节点的编号为 $i$：
- 该节点的左子节点的编号为 $2 \times i + 1$，右子节点的编号为 $2 \times i + 2$。若某个子节点的编号大于等于节点总数 $N$，则该子节点不存在。
- 根节点没有父节点。当 $i>0$ 时，其父节点编号为 $\left\lfloor\frac{i-1}{2}\right\rfloor$。
由于完全二叉树的节点按照层序排列后，父节点和子节点的编号之间存在确定的映射关系，因此我们可以直接使用数组来表示完全二叉树。
堆
定义
堆（Heap）是一种满足特定条件的完全二叉树。
根据节点之间的大小关系，可以分为大顶堆和小顶堆：
- 大顶堆（Max Heap）：任意节点的值 ≥ 其子节点的值。
- 小顶堆（Min Heap）：任意节点的值 ≤ 其子节点的值。
小顶堆示例：
大顶堆示例：
我们将这颗二叉树的根节点称为 “堆顶” ，将最后一层的最后一个节点称为 “堆底”：
不难发现，大顶堆（小顶堆）的堆顶是整个堆的最大（最小）值。
作用
堆可以高效地维护一组数据中的最值。
例如，大顶堆能够保证堆顶元素始终是当前堆中的最大值，因此每次取出堆顶元素，都可以取得当前堆中的最大值。
堆的常用操作
堆最重要的两个操作是添加元素、取出堆顶元素。
我们定义如下的方法签名：
void push(E e)：往堆中添加元素。E pop()：取出堆顶元素。
这两个操作都可能破坏堆的性质，因此，如何在添加或删除元素之后恢复堆的性质，是这两个操作需要解决的核心问题，也是我们实现代码时的重难点。
实现大顶堆
目标
我们自己创建一个大顶堆类，要用上之前讲到过的数组表示。为了演示方便起见，数组元素是Integer类型的。
我们定义的初始结构如下：
▼java复制代码public class MyMaxHeap { private final List<Integer> data; public MyMaxHeap() { data = new ArrayList<>(); } public void push(Integer e) { // TODO } public Integer pop() { // TODO return null; } }
添加元素
以如下大顶堆为例，假设我们现在想加入新元素 7：
第一个问题来了：新元素插在哪？
为了不破坏完全二叉树的性质，新元素应该插入到当前完全二叉树的最后一个位置，也就是数组的末尾。
不难发现，这明显不符合大顶堆的性质，因为此时子节点的值大于其父节点的值。
既然如此，那我们不妨交换这两个节点的值，像这样：
之后继续将当前节点的值与父节点的值进行比较。如果当前节点的值大于父节点的值，就交换二者的值，并继续向上比较，直到当前节点没有父节点，或者当前节点的值不再大于父节点的值为止。
经过不断与父节点比较并交换，这个新元素最终上浮到了满足大顶堆性质的位置：
思路理清楚了，接下来就开始实现 push 方法的核心逻辑吧！
我的参考实现如下：
▼java复制代码public void push(Integer e) { data.add(e); int curIdx = data.size() - 1; int parentIdx = (curIdx - 1) / 2; while (curIdx > 0) { if (data.get(parentIdx) >= data.get(curIdx)) { break; } // 上浮 int t = data.get(parentIdx); data.set(parentIdx, e); data.set(curIdx, t); curIdx = parentIdx; parentIdx = (curIdx - 1) / 2; } }
取出堆顶元素
现在我们要取出当前的堆顶元素 9：
如何在不破坏完全二叉树这一核心性质的基础上，取出堆顶元素呢？
首先，直接删除堆顶元素是不行的，为了保全完全二叉树的性质，显然我们只能对堆底元素动手。
既然如此，那我们不妨先交换堆顶和堆底的元素，例如：
这样，原来的堆顶元素 9 不就可以顺利取出了么？
不难发现，这明显不符合大顶堆的性质，因为此时父节点的值小于其子节点。
为了恢复大顶堆的性质，我们的核心思路和之前的类似，即通过不断比较和交换，将它调整到满足大顶堆性质的位置。
现在 5 应该和谁交换呢？
显然，应该和子节点中最大的那一个交换，这样才能保证大顶堆的性质：
之后继续将当前节点的值与子节点中最大的值进行比较。如果当前节点的值小于该子节点的值，就交换二者的值，并继续向下比较，直到当前节点没有子节点，或者当前节点的值不小于所有子节点的值为止。
经过不断与父节点比较并交换，这个新上位的 5 最终下沉到了满足大顶堆性质的位置：
思路理清楚了，接下来就开始实现 pop 方法的核心逻辑吧！
我的参考实现如下：
▼java复制代码public Integer pop() { if (data.isEmpty()) { throw new RuntimeException("非法操作！"); } int bottomIdx = data.size() - 1; int t = data.get(0); data.set(0, data.get(bottomIdx)); data.set(bottomIdx, t); int result = data.remove(bottomIdx); /* 在完全二叉树中，一个节点的子节点情况只有如下三种： 1. 左右子节点都存在。 2. 只存在左子节点 3. 没有子节点 可见，如果存在左子节点，则右子节点可能存在，也可能不存在； 如果不存在左子节点，则一定不存在右子节点。 基于完全二叉树的这一特性，后续代码的实现会更加简单。 */ int curIdx = 0; int leftChildIdx = 1; while (leftChildIdx < data.size()) { int rightChildIdx = leftChildIdx + 1; int nextIdx; if (rightChildIdx < data.size()) { // 左右子节点都存在 int maxValue, maxIdx; if (data.get(leftChildIdx) > data.get(rightChildIdx)) { maxIdx = leftChildIdx; maxValue = data.get(leftChildIdx); } else { maxIdx = rightChildIdx; maxValue = data.get(rightChildIdx); } if (data.get(curIdx) >= maxValue) { break; } nextIdx = maxIdx; } else { // 只有左子节点 if (data.get(curIdx) >= data.get(leftChildIdx)) { break; } nextIdx = leftChildIdx; } // 下沉 int t1 = data.get(curIdx); data.set(curIdx, data.get(nextIdx)); data.set(nextIdx, t1); curIdx = nextIdx; leftChildIdx = 2 * curIdx + 1; } return result; }
最后汇总并稍稍优化一下最终的实现：
▼java复制代码public class MyMaxHeap { private final List<Integer> data; public MyMaxHeap() { data = new ArrayList<>(); } public void push(Integer e) { data.add(e); int curIdx = data.size() - 1; int parentIdx = (curIdx - 1) / 2; while (curIdx > 0) { if (data.get(parentIdx) >= data.get(curIdx)) { break; } // 上浮 swap(curIdx, parentIdx); curIdx = parentIdx; parentIdx = (curIdx - 1) / 2; } } public Integer pop() { if (data.isEmpty()) { throw new RuntimeException("非法操作！"); } int bottomIdx = data.size() - 1; swap(0, bottomIdx); int result = data.remove(bottomIdx); /* 在完全二叉树中，一个节点的子节点情况只有如下三种： 1. 左右子节点都存在。 2. 只存在左子节点 3. 没有子节点 可见，如果存在左子节点，则右子节点可能存在，也可能不存在； 如果不存在左子节点，则一定不存在右子节点。 基于完全二叉树的这一特性，后续代码的实现会更加简单。 */ int curIdx = 0; int leftChildIdx = 1; while (leftChildIdx < data.size()) { // 这就是为什么我要把右子节点的下标索引定义在这个位置。 int rightChildIdx = leftChildIdx + 1; int nextIdx; if (rightChildIdx < data.size()) { // 左右子节点都存在 int maxValue, maxIdx; if (data.get(leftChildIdx) > data.get(rightChildIdx)) { maxIdx = leftChildIdx; maxValue = data.get(leftChildIdx); } else { maxIdx = rightChildIdx; maxValue = data.get(rightChildIdx); } if (data.get(curIdx) >= maxValue) { break; } nextIdx = maxIdx; } else { // 只有左子节点 if (data.get(curIdx) >= data.get(leftChildIdx)) { break; } nextIdx = leftChildIdx; } // 下沉 swap(curIdx, nextIdx); curIdx = nextIdx; leftChildIdx = 2 * curIdx + 1; } return result; } /** * 交换 data[i] 和 data[j] 这两个元素 */ private void swap(int i, int j) { int t = data.get(i); data.set(i, data.get(j)); data.set(j, t); } }
然后我们简单分析一下恢复大顶堆性质的过程中的时间复杂度。
具体要交换多少次其实取决于树高。我们考虑最坏的情况，也就是一路从堆顶交换到叶子节点这一层。最多需要 O(log N) 次交换。因此，每一次取出堆顶元素和添加元素的时间复杂度都是 O(log N)。
大顶堆都会写了，那么小顶堆对你来说还是什么难题么？快去试试吧！
Java 中的优先队列
Java 的集合框架中的 优先队列（PriorityQueue） 是对于堆的实现。
它默认使用元素的自然顺序来确定优先级。例如：
▼java复制代码PriorityQueue<Integer> heap = new PriorityQueue<>();
这创建出来的就是一个关于Integer的小顶堆，因为 Integer 的自然排序是按照升序来排的。
要让其为大顶堆，我们需要传入自定义比较器：
▼java复制代码PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> Integer.compare(o2,o1));
以下是一个示例：
▼java复制代码PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> Integer.compare(o2,o1)); heap.offer(9); heap.offer(10); heap.offer(5); heap.offer(7); heap.offer(8); heap.offer(1); heap.offer(2); while (!heap.isEmpty()) { System.out.println(heap.poll()); }
最后按照降序依次输出：
▼text复制代码10 9 8 7 5 2 1
学完堆的这些内容后，你可以尝试去做一道非常经典的题目：23. 合并 K 个升序链表 。
堆排序
在刚学完堆的核心知识后，我们再来学习一个基于堆的经典排序算法——堆排序。
假如给你一个乱序的整数数组，现在要求将它按照升序排列。
现在你应该可以想到：先利用小顶堆将数组中的所有元素建堆，然后不断取出堆顶的最小值，并从左往右依次填入原数组。这样原数组就排好序了。
不过，这种做法需要额外的空间来存储堆。而堆排序真正有意思的地方在于：我们可以直接在原数组上建堆。
首先，我们先从左往右遍历每个元素，把它们添加到堆中。设堆底下标为i，则区间[0,i]就是原数组中的堆。
然后我们不断从堆中取出元素。回顾一下，在取出堆顶元素时，我们会先交换堆顶和堆底的元素，然后删除堆底元素，再对剩余的堆进行下沉。
而在堆排序中，我们不需要真正删除这个堆底元素，只需要让它留在原数组中，并缩小堆的有效范围。这样，每次取出的最值元素都会被放到数组末尾。最终，整个数组就是升序的了。
现在考虑升序和降序分别应该使用什么堆？你先自己思考一下。
—— 升序用大顶堆，降序用小顶堆。
思路理清楚了，接下来就开始代码实现吧。
我的参考实现如下：
▼java复制代码/** * 堆排序 */ public void heapSort(int[] arr) { if (arr.length <= 1) { return; } // 在原数组上直接建大顶堆 for (int i = 0; i < arr.length; i++) { int curIdx = i; int parentIdx = (curIdx - 1) / 2; while (curIdx > 0) { if (arr[curIdx] <= arr[parentIdx]) { break; } // 上浮 swap(arr, curIdx, parentIdx); curIdx = parentIdx; parentIdx = (curIdx - 1) / 2; } } // 取出堆中的所有元素 for (int i = 0; i < arr.length; i++) { // 记录此时取出元素前的堆大小 int size = arr.length - i; swap(arr, 0, size - 1); size--; int curIdx = 0; int leftChildIdx = 1; while (leftChildIdx < size) { int rightChildIdx = leftChildIdx + 1; int nextIdx; if (rightChildIdx < size) { // 左右孩子都有 int maxValue, maxIdx; if (arr[leftChildIdx] > arr[rightChildIdx]) { maxIdx = leftChildIdx; maxValue = arr[leftChildIdx]; } else { maxIdx = rightChildIdx; maxValue = arr[rightChildIdx]; } if (arr[curIdx] >= maxValue) { break; } nextIdx = maxIdx; } else { // 只有左孩子 if (arr[curIdx] >= arr[leftChildIdx]) { break; } nextIdx = leftChildIdx; } // 下沉 swap(arr, curIdx, nextIdx); curIdx = nextIdx; leftChildIdx = 2 * curIdx + 1; } } } /** * 用于交换arr[i]和arr[j]这两个元素 */ private void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
在这份实现中，每插入一个元素都需要进行一次上浮操作，每次上浮的时间复杂度为 O(logN)，因此建堆的时间复杂度为 O(NlogN)。之后，我们还需要依次取出每个元素，每次取出都需要进行一次下沉操作，时间复杂度为 O(logN)，因此这一部分的时间复杂度也是 O(NlogN)。两部分是依次执行的，所以堆排序的总时间复杂度为 O(NlogN)。
理解上面所说的之后，你便可以用堆排序来解决这道题目了：912. 排序数组。
