特殊的二叉树-堆结构及其在排序中的应用
完全二叉树
- 从第一层到倒数第二层，每一层都是满的，也就是说每一层的结点数都达到了当前层所能达到的最大值
- 最后一层的结点是从左到右连续排列的，不存在跳跃排列的情况（也就是说这一层的所有结点都集中排列在最左边）。
注意，完全二叉树中有着这样的索引规律：假如我们从左到右、从上到下依次对完全二叉树中的结点从 0 开始进行编码：
那么对于索引为 n 的结点来说：
- 索引为 (n-1)/2 的结点是它的父结点
- 索引 2*n+1 的结点是它的左孩子结点
- 索为引 2*n+2 的结点是它的右孩子结点
什么是堆
堆是完全二叉树的一种特例。根据约束规则的不同，堆又分为两种：
- 大顶堆
如果对一棵完全二叉树来说，它每个结点的结点值都不小于其左右孩子的结点值，这样的完全二叉树就叫做“大顶堆”
- 小顶堆
树中每个结点值都不大于其左右孩子的结点值，这样的完全二叉树就叫做“小顶堆”
堆的基本操作：以大顶堆为例
我们需要关注的动作有两个：
- 如何取出堆顶元素（删除操作）
- 往堆里追加一个元素（插入操作）
至于堆的初始化，也只不过是从空堆开始，重复执行动作 2 而已。因此，上面这两个动作就是堆操作的核心。
假设一个完全二叉树的层序遍历的结果
[9, 8, 6, 3, 1]
取出堆顶元素
取出元素本身并不难，难的是如何在删除元素的同时，保持住队的“大顶”结构特性。为了做到这点，我们需要执行以下操作：
- 用堆里的最后一个元素（对应图中的数字 1）替换掉堆顶元素。
- 对比新的堆顶元素（1）与其左右孩子的值，如果其中一个孩子大于堆顶元素，则交换两者的位置
- 交换后，继续向下对比 1 与当前左右孩子的值，如果其中一个大于 1，则交换两者的位置
重复这个向下对比+交换的过程，直到无法继续交换为止，我们就得到了一个符合“大顶”原则的新的堆结构
// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function downHeap(low, high) {
// 初始化 i 为当前结点，j 为当前结点的左孩子
let i = low,
j = i * 2 + 1;
// 当 j 不超过上界时，重复向下对比+交换的操作
while (j <= high) {
// 如果右孩子比左孩子更大，则用右孩子和根结点比较
if (j + 1 <= high && heap[j + 1] > heap[j]) {
j = j + 1;
}
// 若当前结点比孩子结点小，则交换两者的位置，把较大的结点“拱上去”
if (heap[i] < heap[j]) {
// 交换位置
const temp = heap[j];
heap[j] = heap[i];
heap[i] = temp;
// i 更新为被交换的孩子结点的索引
i = j;
// j 更新为孩子结点的左孩子的索引
j = j * 2 + 1;
} else {
break;
}
}
}
往堆里追加一个元素
当添加一个新元素进堆的时候，我们同样需要考虑堆结构的排序原则：
新来的数据首先要追加到当前堆里最后一个元素的后面。比如我现在要新增一个 10，它就应该排在最后一层的最后一个位置
不断进行向上对比+交换的操作：如果发现 10 比父结点的结点值要大，那么就和父结点的元素相互交换，再接着往上进行比较，直到无法再继续交换为止
// 入参是堆元素在数组里的索引范围，low表示下界，high表示上界
function upHeap(low, high) {
// 初始化 i（当前结点索引）为上界
let i = high;
// 初始化 j 为 i 的父结点
let j = Math.floor((i - 1) / 2);
// 当 j 不逾越下界时，重复向上对比+交换的过程
while (j >= low) {
// 若当前结点比父结点大
if (heap[j] < heap[i]) {
// 交换当前结点与父结点，保持父结点是较大的一个
const temp = heap[j];
heap[j] = heap[i];
heap[i] = temp;
// i更新为被交换父结点的位置
i = j;
// j更新为父结点的父结点
j = Math.floor((i - 1) / 2);
} else {
break;
}
}
}
尤其是要记住这几个关键字：“删除”就是“向下比较+交换”，而“添加”则是“向上比较+交换”。
堆结构在排序中的应用 —— 优先队列
题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
- 方法一：数组从大到小排序，对应 k-1 下标
- 方法二：构造大小为 k 的小顶堆
function findKthLargest(nums, k) {
// 将数组逆序
const sorted = nums.sort((a, b) => {
return b - a;
});
// 取第k大的元素
return sorted[k - 1];
}
面试的时候，万一被问到“你为什么不会写 xx 排序算法”，这时候用一句“我用 sort 方法比较多，不喜欢自己造轮子”糊弄过去，还是有一定成功率的。
对于这道题来说，要想求出第 k 大的元素，我们可以维护一个大小为 k 的小顶堆。这个堆的初始化过程可以通过遍历并插入数组的前 k 个元素来实现。当堆被填满后，再尝试用数组的第 k+1 到末尾的这部分元素来更新这个小顶堆，更新过程中遵循以下原则：
- 若遍历到的数字比小顶堆的堆顶元素值大，则用该数字替换掉小顶堆的堆顶元素值
- 若遍历到的数字比小顶堆的堆顶元素值小，则忽略这个数字
仔细想想，为什么要这样做？假设数组中元素的总个数是 n，那么：
- 维护大小为 k 的小顶堆的目的，是为了确保堆中除了堆顶元素之外的 k-1 个元素值都大于堆顶元素。
- 当我们用数组的[0, k-1]区间里的 数字初始化完成这个堆时，堆顶元素值就对应着前 k 个数字里的最小值。
- 紧接着我们尝试用索引区间为 [k, n-1]的数字来更新堆，在这个过程中，只允许比堆顶元素大的值进入堆。这一波操作过后，堆里的 k 个数字就是整个数组中最大的 k 个数字，而堆顶的数字正是这 k 个数中最小的那个。于是本题得解。
function findKthLargest(nums, k) {
const heap = [];
const len = nums.length;
const n = 0;
function createHeap() {
for (let i = 0; i < k; i++) {
insert(nums[i]);
}
}
function updateHeap() {
for (let i = k; i < len; i++) {
if (nums[i] > heap[0]) {
heap[0] = nums[i];
downHeap(0, k);
}
}
}
function downHeap(low, high) {
let i = low;
let j = 2 * low + 1;
while (j <= high) {
if (j + 1 <= high && heap[j + 1] < heap[j]) {
j = j + 1;
}
if (heap[i] > heap[j]) {
[heap[i], heap[j]] = [heap[j], heap[i]];
i = j;
j = 2 * i + 1;
} else {
break;
}
}
}
function insert(x) {
heap[n] = x;
upHeap(0, n);
n++;
}
function upHeap(low, high) {
let i = high;
let j = Math.floor((i - 1) / 2);
while (j >= low) {
if (heap[j] > heap[i]) {
[heap[i], heap[j]] = [heap[j], heap[i]];
i = j;
j = Math.floor((i - 1) / 2);
} else {
break;
}
}
}
createHeap();
updateHeap();
return heap[0];
}
编码复盘
上面这个题解中出现的 heap 数组，就是一个优先队列。
优先队列的本质是二叉堆结构，它具有以下特性：
- 队列的头部元素，也即索引为 0 的元素，就是整个数组里的最值——最大值或者最小值
- 对于索引为 i 的元素来说，它的父结点下标是 (i-1)/2（上面咱们讲过了，这与完全二叉树的结构特性有关）
- 对于索引为 i 的元素来说，它的左孩子下标应为 2*i+1，右孩子下标应为 2*i+2。
当题目中出现类似于“第 k 大”或者“第 k 高“这样的关键字时，就是在暗示你用优先队列/堆结构来做题——这样的手法可以允许我们在不对序列进行完全排序的情况下，找到第 k 个最值。