前言
为什么说树结构是01世界里最重要的数据结构，因为只要调整一下节点的存储顺序或枝杈多少，解决问题的类型就可以完全不同。本章介绍的堆也是二叉树的一种，与二叉搜索树想比，只是改变了节点存放值的规则，它遵循的规则就是每个父节点的值必须大于或等于孩子节点的值，这种数据结构是二叉堆，也可以叫它优先队列。
什么是优先队列？
上一章我们介绍了普通队列，固定的从队尾入队，从队首出队。假如现在的场景需求是，出队时每次必须出队优先级最高的元素，你可能会说，这还不简单么，只需要出队时遍历整个队列，从里面找到优先级最高的元素出队，然后再队列里移除该元素即可。这样确实能满足场景的需求，但也会出现一个问题，就是出队效率太低，如果使用的是数组，找到优先级最高的元素需要O(n)的时间，然后出队该元素数组又需要O(n)的位移操作，也就是说每次出队需要消耗O(n²)的时间，这个有点太奢侈。
而堆这种数组结构就是专门用来解决这一类的问题，同样是使用数组，同样每次出队优先级最高的元素，却可以把入队和出队的操作稳定的保持在O(logn)，虽然普通队列入队是O(1)，但从入队出队的平均复杂度来看，性能的差距是O(log)与O(n²)。我们来看下在处理十万条数据的出队/入队时，堆与普通队列之间的性能差距。
image
百万级别的数据时家用机已经卡死，而堆依然可以一秒之内处理完，并且随着数据规模的增加，它们之间的性能差距倍数只会越来越大。
什么是堆？
[37, 22, 26, 12, 11, 25, 7, 3, 8, 10]，初看起来这是一个数组，但如果我们把它按照二叉树的结构排列起来，就会出现图下的结构：
image
而这就是一个堆，它有几个特点：
1. 父节点优先级高于或等于子节点
堆最显著的特点就是所有父节点的优先级都高于或等于孩子节点。这里的堆为最大堆，根节点的值最大，任意节点的排列顺序皆是如此。还有最小堆，也就是所有父节点的值小于或等于孩子节点，根节点的值最小。
2. 完全二叉树
堆的排列都是一颗完全二叉树，除去最底层的叶子节点，它就是一颗满二叉树，而且所有的叶子节点全部都朝树的左侧摆放。之前二叉树特性章节已经有所说明，只要是满二叉树使用数组是最佳存储方式。
3. 动态性
与二叉搜索树类似，当往构建好的堆内再添加或取出元素时，为了不破坏堆的性质，堆有自己的一套操作，无论何时添加/移除多少元素，始终不会破坏堆的性质。
从零实现最大堆
使用数组来表示二叉树，最大的问题是当前节点没有指向孩子节点的指针，其实这问题很好解决，通过当前节点的下标可以求出它的父节点和左右孩子节点，这也是使用数组存储的优势：
image
解决了这个难点后，我们首先写出最大堆的辅助函数：
class MaxHeap {
constructor() {
this._data = [] // 存储堆里的数据
}
getParent(i) { // 获取父节点
return (i - 1) / 2 | 0 // 向下取整
}
getLeftChild(i) { // 获取左孩子
return i * 2 + 1
}
getRightChild(i) { // 获取右孩子
return i * 2 + 2
}
}
增(siftUp)
往堆里添加任意元素而又不能破坏堆的性质，首先将添加的元素推入堆数组的末尾，然后这个元素需要与自己的父节点进行比较，如果比父节点大，那么它们之间就需要位置交换。交换位置之后继续与之前当前位置的父节点进行比较，如果还是比父节点大，就继续交换，直到遇到不大于父节点或已经达到根节点为止。这个操作也叫siftUp，让节点一步步的进行上浮。
image
class MaxHeap {
constructor() {
this._data = [] // 存储堆里的数据
}
...
push(val) {
this._data.push(val) // 添加到队尾
this.siftUp(this._data.length - 1) // 上浮队尾元素
}
siftUp(i) {
const parent = this.getParent(i) // 获取父节点的值
if (this._data[i] > this._data[parent]) { // 如果大于父节点的值
this.swap(i, parent) // 交换位置
this.siftUp(parent) // 继续上浮
}
}
swap(i, j) { // 交换数组两个元素的位置
[this._data[i], this._data[j]] = [this._data[j], this._data[i]]
}
}
取(siftDown)
费了这么多事，都是为了出队的元素是优先级最高的，很明显，直接出队堆顶的元素即可，但出队后，根节点就为空，这个时候就破坏了堆的性质。所以堆又有对应的出队操作siftDown，堆顶出队后，将堆数组的最后一个元素放入堆顶，然后将堆顶的元素与它的左右孩子进行比较，与其中最大值的孩子交换位置，直至大于两个孩子节点或到达根节点即可。
image
class MaxHeap {
constructor() {
this._data = [] // 存储堆里的数据
}
...
sift() { // 出队
if (this._data.length === 0) {
return
}
const max = this._data[0] // 缓存出队元素
this.swap(0, this._data.length - 1) // 顶尾交换
this._data.pop() // 移除队尾
this.siftDown(0) // 将换上来的节点进行下沉
return max // 返回应该出队的元素
}
siftDown() {
const { _data } = this
let max = this.getLeftChild(i) // 假如左孩子大
if (max >= _data.length) { // 左孩子界限超出，递归终止
return
}
if (max + 1 < _data.length && _data[max + 1] > _data[max]) {
// 如果有右孩子且右孩子比左孩子大，max+1变为右孩子的下标
max++
}
if (_data[i] < _data[max]) { // 如果孩子节点大于当前节点，执行下沉操作
this.swap(i, max) // 交换当前节点与孩子节点的位置
this.siftDown(max) // 在孩子节点的位置继续递归
}
}
}
下沉操作的关键是找到两个孩子节点里面比较大的那位进行交换，交换之后在孩子节点的位置进行递归即可。以上就是堆最重要两个操作，入队和出队，已经算是从零完成了堆，不过有两个堆的辅助函数，可以更加方便快速的完成堆的相应操作。
替换(replace)
现在有一个需求是出队的同时，添加一个值到堆里，可以使用前面实现的两个方法方式，首先sift取出堆顶元素，然后push进一个元素即可，不过这样的话会执行两次O(logn)的操作，我们可以封装一个replace方法，执行一次O(logn)即可。
class MaxHeap {
constructor() {
this._data = [] // 存储堆里的数据
}
...
replace(val) {
if (this._data.length === 0) {
return
}
const max = this._data[0] // 缓存出队元素
this._data[0] = val // 将添加的元素赋值给堆顶
this.siftDown(0) // 堆顶执行下沉操作
return max // 出队
}
}
数组快速堆化(heapify)
如何将一个数组快速转换为堆？直接把数组的每一项遍历添加到堆里即可，这样确实可以实现，但这个过程并不是最快的。这里我们可以借助完全二叉树的特性，以最后一个叶子节点的父节点为起点，把起点节点到根节点之间的所有节点进行下沉操作即可。这样的话，平均可以省去一半节点的操作，通过我看不懂的证明得知可从O(nlogn)变为O(n)的复杂度。
image
class MaxHeap {
constructor(arr = []) { // 构造函数支持传入数组，快速堆化
if (Array.isArray(arr) && arr.length > 0) {
this._data = [...arr]
this.heapify(this._data)
} else {
this._data = [] // 存储堆里的数据
}
}
...
heapify(arr) {
let parent = this.getParent(arr.length - 1)
while (parent >= 0) {
this.siftDown(parent)
parent--
}
}
}
堆的应用
以上代码我们从零实现了一个堆，但它有什么用了？接下来介绍几个示例来说明这种数据结构的作用，及在处理特定问题时的巧妙。
堆排序 ↓
从上面实现的最大堆不难发现，既然每次堆顶都是最大的值，那我们依次出队整个堆，那不实现了一次降序的排序么？依照这个特性，构建一个最小堆来实现一个排序算法试试！
function heapSort(arr) {
let last = ((arr.length - 2) / 2) | 0; // 只需要从最后一个叶子的父节点开始
const ret = [];
while (last >= 0) {
siftDown(arr, last, arr.length); // 下沉一半的节点实现堆化
last--;
}
while (arr.length > 0) {
ret.push(arr[0]); // 将堆顶元素放入新数组内
[arr[0], arr[arr.length - 1]] = [arr[arr.length - 1], arr[0]]; // 交换首尾的元素
arr.pop(); // 将交换的堆顶元素去掉
siftDown(arr, 0, arr.length); // 重新下沉堆顶，不破坏堆的性质
}
return ret; // 返回排序好的数组
function siftDown(arr, i, n) {
let left = i * 2 + 1;
if (left >= n) {
return;
}
if (left + 1 < n && arr[left] > arr[left + 1]) { // 改为判断谁小谁 +1
left++;
}
if (arr[left] < arr[i]) { // 让大元素下沉
[arr[left], arr[i]] = [arr[i], arr[left]];
siftDown(arr, left, n);
}
}
}
虽然我们完成了排序的任务，但这个算法我们另外开辟了O(n)的空间去存放新的排序好的数组，那有没可能省掉这个额外的空间了，答案是有的，可以使用原地堆排序的方式，我们来实现它！
原地堆排序 ↓
也就是在原数组上直接进行排序，而不借助额外空间，它的实现原理是使用最大堆，构建好了之后将堆顶元素与末尾进行交换，而后缩小右边界，重新构建堆，依次执行上述过程即可。
image
function heapSort(arr) {
let last = ((arr.length - 1) / 2) | 0;
while (last >= 0) {
siftDown(arr, last, arr.length); // 使用最大堆
last--;
}
let r = arr.length;
while (r > 0) {
[arr[0], arr[r - 1]] = [arr[r - 1], arr[0]]; // 将堆顶与末尾元素交换
r--; // 右边界减1
siftDown(arr, 0, r); // 重新下沉堆顶元素
}
function siftDown (arr, i, n) {
let left = i * 2 + 1;
if (left >= n) {
return;
}
if (left + 1 < n && arr[left] < arr[left + 1]) { // 大顶堆
left++;
}
if (arr[i] < arr[left]) { // 下沉小元素
[arr[i], arr[left]] = [arr[left], arr[i]];
siftDown(arr, left, n);
}
};
}
1046-最后一块石头的重量 ↓
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。
假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x === y，那么两块石头都会被完全粉碎；
如果 x !== y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
这题取巧的地方就在于每次要找到最大的两块石头，那我们使用最大堆来解这题就非常适合了，取两次堆顶的元素元素即可，而后把相减的绝对值放入堆顶，重新下沉一次维持堆的性质即可，当堆里的元素只剩一个时结束这个过程。代码如下：
const lastStoneWeight = function (stones) {
let last = ((stones.length - 2) / 2) | 0;
while (last >= 0) { // 堆化
siftDown(stones, last);
last--;
}
while (stones.length > 1) { // 当只有一个元素结束循环
swap(stones, 0, stones.length - 1) // 首尾交换
const first = stones.pop() // 取出尾巴里的最大值
siftDown(stones, 0) // 执行下沉维持堆
const second = stones[0] // 再取出堆顶的元素，即为第二大的元素
const diff = Math.abs(first - second) // 求出绝对值
stones[0] = diff // 将绝对值覆盖堆顶
siftDown(stones, 0) // 再次维持堆
}
return stones[0];
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
function siftDown(arr, i) {
let left = i * 2 + 1;
if (left >= arr.length) {
return;
}
if (left + 1 < arr.length && arr[left] < arr[left + 1]) {
left++;
}
if (arr[left] > arr[i]) {
swap(arr, left, i)
siftDown(arr, left);
}
}
};
堆是用的数组实现，所以尽可能的不让数组有位移的操作，这个非常有必要考虑。
215-数组中的第K个最大元素 ↓
最简单的解法就是先使用sort函数排序，然后选取对应下标的元素即可，但如果面试官出了这个题目，那么想看到肯定就不是这么一个O(nlogn)的暴力解法了，借助本章学习的堆，我们可以交出O(nlogk)的解法。如果是求100万数据的第100大小的数字，这个优化还是很有益的。
首先说明思路，构建一个k大小的最小堆，之后遇到的元素如果大于堆顶，就替换堆顶的元素，执行下沉操作，保持堆的性质，最后当整个数组遍历完，这个最小堆的堆顶就是需要返回的元素了，因为比第k大的全部在堆顶的下面。
var findKthLargest = function (nums, k) {
const minHeap = [] // 最小堆
for (let i = 0; i < nums.length; i++) {
if (i < k) { // 堆的大小还没达到k
minHeap.push(nums[i]) // 直接push
siftUp(minHeap, minHeap.length - 1) // 执行上浮操作维持堆的性质
} else if (nums[i] > minHeap[0]) { // 如果下一个元素大于堆顶
minHeap[0] = nums[i] // 替换堆顶元素
siftDown(minHeap, 0) // 执行下沉操作维持堆性质
}
}
return minHeap[0] // 最后返回最小堆堆顶元素即可
};
function siftUp(nums, i) {
const parent = (i - 1) / 2 | 0
if (nums[i] < nums[parent]) { // 将小的元素上浮
swap(nums, i, parent)
siftUp(nums, parent)
}
}
function siftDown(nums, i) {
let l = i * 2 + 1
if (l + 1 > nums.length) {
return
}
if (l + 1 <= nums.length && nums[l] > nums[l + 1]) {
l++ // 选取小的元素
}
if (nums[i] > nums[l]) { // 将大的元素下沉
swap(nums, i, l)
siftDown(nums, l)
}
}
function swap(nums, i, parent) {
[nums[i], nums[parent]] = [nums[parent], nums[i]]
}
373-查找和最小的K对数字 ↓
给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
依次遍历嵌套的两个数组，这个是无可避免的，但这题我们能优化的是这个计算结果的存放，不使用暴力的每次计算后进行排序。使用堆即可，维持一个k大小的最大堆，每次计算的值与堆顶元素进行比较，如果比堆顶的小，就放入堆里，最后重新排序这个k大小的堆即可。
var kSmallestPairs = function (nums1, nums2, k) {
const heap = []
for (let i = 0; i < nums1.length; i++) {
for (let j = 0; j < nums2.length; j++) {
if (heap.length === k && nums1[i] + nums2[j] >= (heap[0][0] + heap[0][1])) {
// 因为都是升序的数组，所以当这次的和大于堆顶时，
// 那么之后的循环也一定是大于的，所以跳出这轮循环即可。
break
}
if (heap.length < k) { // 堆没有满时
heap.push([nums1[i], nums2[j]])
siftUp(heap, heap.length - 1) // 构建最大堆
} else if ((nums1[i] + nums2[j]) <= sum(heap[0])) { // 只有当小于堆顶时
heap[0] = [nums1[i], nums2[j]] // 替换堆顶的元素
siftDown(heap, 0) // 维持最大堆
}
}
}
return heap.sort((a, b) => (a[0] + a[1]) - (b[0] + b[1]))
// 因为是最大堆，所有返回升序的顺序
};
function siftUp(heap, i) {
const parent = (i - 1) / 2 | 0
if (sum(heap[i]) > sum(heap[parent])) {
swap(heap, i, parent)
siftUp(heap, parent)
}
}
function siftDown(heap, i) {
let left = i * 2 + 1
if (left >= heap.length) {
return
}
if (left + 1 < heap.length && sum(heap[left]) < sum(heap[left + 1])) {
left++
}
if (sum(heap[i]) <= sum(heap[left])) {
swap(heap, i, left)
siftDown(heap, left)
}
}
function sum(arr) { // 求和
return arr[0] + arr[1]
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
最后
写了这么多，不难发现无非就是siftup和siftdown函数的编写， 只要熟练掌握堆的这两种操作，基本上来说堆也就掌握了90%。还有最主要的是熟悉堆的思想，针对前k类似的题目，使用堆都是非常适合的，而堆的动态性又非常适合处理数据随时有新元素加入的场景。居然有这么cool的数据结构~ 本章github源码
网友评论