说在前面
计算机领域里，到处都是算法，算法的运用是如此常见，如此自然，如此平凡，乃至像空气一样，会被绝大多数人，甚至是计算机专业的人忽视。从我们打开计算机（或者手机，平板电脑）开始，一系列算法就开始运转起来。从操作系统的调度算法，帮助我们顺畅地使用操作系统；到网络连接过程中各种协议的运转，帮助我们畅游信息世界；从我们使用搜索引擎，一个简单的关键字就可以在毫秒级别的时间返回数以亿计的信息，按照优先级排列展现到我们眼前；到浏览器将枯燥的 html, css 和 js 文本转换成直观的网页，供我们轻松阅读浏览；从看似平凡的文字处理工具帮助我们排版，修订；到图像工具中各种神奇的滤镜帮助我们磨皮修片；从游戏，影视作品中炫酷的特效；到最新的交互科技——无论是 AR 还是 VR，越来越普遍的应用，算法无处不在。
说实话，现在，我的这个“学习计算机，必须要懂算法”的观点在逐渐转变。这是因为，计算机的软件行业也在渐渐走向成熟。软件行业已经慢慢成熟到了：如果不会算法，也完全可以有所作为的程度。这也是很多人觉得算法没必要的一个主要原因。
但是，大家一定要提醒自己。虽然我说学习算法对你来说不一定有用，但与此相对应的，要想取得成功，就一定有别的什么，是有用的。算法不是技术领域的唯一的核心竞争力，但无论是一个人，一个企业，还是做一份事业，都需要有核心竞争力。什么都没有，肯定是不行的。
说到算法，一定离不开数据结构，所以对于一些基础的数据结构，我们还是要掌握的，今天就让我们一起先来看看
堆。
什么是堆？
堆的定义
堆的数据结构是完全二叉树或一堆数组，因为堆在逻辑上是一棵完全二叉树，在物理结构上是一个一维数组。堆将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。 堆是非线性数据结构，相当于一维数组,有两个直接后继。堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
堆的性质
- 1、堆中某个节点的值总是不大于或不小于其父节点的值；
- 2、堆总是一棵完全二叉树
堆的常用用途：
- 构建优先队列
- 支持堆排序
- 快速找出一个集合中的最小值（或者最大值）
实现思路
使用数组实现堆
堆总是一棵完全二叉树，如下图：
根据堆的这个性质，我们可以使用数组来实现，我们只需要记住父子节点之间的关系即可，假设一个节点的下标为 n,我们可以得到以下信息：
- 1、父节点下标
fatherIdx = Math.floor((n - 1) / 2);
- 2、左子节点下标
leftInd = n * 2 + 1;
- 3、右子节点下标
rightInd = (n + 1) * 2 = leftInd + 1;
所以我们可以直接将该二叉树转换为数组来进行存储，根据以上公式我们可以快速的在数组中找到每个元素的父子元素。
初始化
初始化一个空数组用于存储堆数据，接受传入一个自定义比较函数，并将传入用于初始化的数据插入堆数组中。
/** * 堆初始化 * @param Array array 用于初始化的数组 * @param Function compareFun 自定义比较函数 * */ constructor(array = [], compareFun = null) { this.queue = []; if (compareFun) { this.compareFun = compareFun; } for (let index = 0; index < array.length; index++) { this.push(array[index]); } }
插入元素
将元素插入到堆数组的最后，因为堆中某个节点的值总是不大于或不小于其父节点的值,所以我们需要根据其比较函数来对堆数组进行调整，将底部插入的元素进行上浮操作，直到满足堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值。
我们以小顶堆为例：
- 1.如果我们发现插入的新元素之后，新插入的元素比起父节点元素值要小，这样就破坏了我们的堆结构，这样就不构成小顶堆。因此我们需要对该结构进行调整。
- 2.由于堆的物理结构是一个数组，所以我们可以通过数组下标的形式找到我们孩子节点的父节点。前面我们已经知道父节点与子节点的下标关系为
fatherIdx = Math.floor((n - 1) / 2);。当我们找到父节点时，我们进行大小比较，如果子节点小于父节点，此时就要进行交换元素。再让子节点到父节点的位置，重新计算父节点。如果子节点大于父节点，此时即说明调整结束。 - 3.持续循环比较，
如果子节点已经上浮到堆顶，说明向上调整结束。
push(node) { this.queue.push(node); this.swim(); } //上浮 swim() { let curIdx = this.queue.length - 1; let fatherIdx = Math.floor((curIdx - 1) / 2); while (this.compareFun(this.queue[fatherIdx], this.queue[curIdx])) { [this.queue[curIdx], this.queue[fatherIdx]] = [ this.queue[fatherIdx], this.queue[curIdx], ]; curIdx = fatherIdx; fatherIdx = Math.floor((curIdx - 1) / 2); } }
获取堆顶元素值
因为每次插入一个元素的时候我们我们都会对其进行一个上浮操作，所以数组第一个元素就是符合规则的栈顶元素，我们只需要判断堆是否为空，不为空则返回数组的第一个元素即可。
front() { if (this.queue.length == 0) return null; return this.queue[0]; }
弹出堆顶元素
我们要弹出堆顶元素,实际上就是要删除堆顶的数据，但是我们并不能直接删除堆顶的数据。如果直接删除堆顶的数据，就会破坏堆结构，并且复原的复杂度较高。在这里我们介绍一种方法不仅解决了删除堆的问题，并且复杂度较低。
- 1、首先我们要将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。
- 2、向下调整算法具体步骤(过程步骤如下图)：
- a.我们将堆顶元素和数组最后一个元素交换后，此时堆顶的元素是数组的最后一个元素，我们要进行向下调整。定义 parent 为堆顶元素，查找 2 个子节点中较小的一个节点作为孩子节点。由于堆是数组结构实现，我们可以首先找到左孩子节点，让左孩子和右孩子进行比较，较小的作为 child 的最后值。
- b.如果孩子小于父亲，则交换，并继续往下调整。让 parent 到 child 的位置，再重新计算孩子。
- c.当孩子节点下标大于等于元素总个数时，循环结束。
注：循环过程中一旦成堆，则跳出循环。
pop() { if (this.queue.length == 0) return null; if (this.queue.length == 1) return this.queue.pop(); const top = this.queue[0]; this.queue[0] = this.queue.pop(); this.sink(); return top; } //下沉 sink() { let curIdx = 0; let minInd = this.getMinInd(curIdx); while (this.compareFun(this.queue[curIdx], this.queue[minInd])) { [this.queue[curIdx], this.queue[minInd]] = [ this.queue[minInd], this.queue[curIdx], ]; curIdx = minInd; minInd = this.getMinInd(curIdx); } } //获取较小的子元素下标 getMinInd(curIdx) { let leftInd = curIdx * 2 + 1; let rightInd = leftInd + 1; let minInd = leftInd; if ( rightInd < this.queue.length && this.compareFun(this.queue[leftInd], this.queue[rightInd]) ) minInd = rightInd; return minInd; }
堆的分类
大顶堆
在上面实现的堆的基础上，我们传入自定义的比较函数即可：
// 大顶堆 const { Heap } = require("./heap"); class MaxHeap { constructor(array = []) { this.oHeap = new Heap(array, (a, b) => { return a < b; }); } get queue() { return this.oHeap.queue; } front() { return this.oHeap.front(); } pop() { return this.oHeap.pop(); } push() { this.oHeap.push(); } }
小顶堆
在上面实现的堆的基础上，我们传入自定义的比较函数即可：
// 小顶堆 const { Heap } = require("./heap"); class MinHeap { constructor(array = []) { this.oHeap = new Heap(array, (a, b) => { return a > b; }); } get queue() { return this.oHeap.queue; } front() { return this.oHeap.front(); } pop() { return this.oHeap.pop(); } push() { this.oHeap.push(); } }
堆的应用
堆排序
堆排序其实就是利用了堆的性质，先将所有元素构造一个堆，不断的弹出堆顶元素即可达到堆排序的效果。
const { MaxHeap } = require("@jyeontu/structure-jyeontu"); const list = [1, 3, 2, 4, 6, 3, 0, 9, 7]; const res = []; const myMaxHeap = new MaxHeap(list); while (myMaxHeap.front() != null) { res.push(myMaxHeap.pop()); } console.log(res); //[9, 7, 6, 4, 3, 3, 2, 1, 0]
我们也可以利用这个性质来给堆的实现代码添加一个单元测试：
const { Heap, MinHeap, MaxHeap } = require("../../src/Heap/index"); const assert = require("assert"); describe("Heap", function () { describe("checkMaxHeap", function () { it("checkOrder", function () { const list = [1, 3, 2, 4, 6, 3, 0, 9, 7]; const orderList = [...list].sort((a, b) => a - b); const myMaxHeap = new MaxHeap(list); while (myMaxHeap.front() != null) { assert.equal(myMaxHeap.pop(), orderList.pop()); } }); }); describe("checkMinHeap", function () { it("checkOrder", function () { const list = [1, 3, 2, 4, 6, 3, 0, 9, 7]; const orderList = [...list].sort((a, b) => b - a); const myMinHeap = new MinHeap(list); while (myMinHeap.front() != null) { assert.equal(myMinHeap.pop(), orderList.pop()); } }); }); });
源码地址
Gitee： https://gitee.com/zheng_yongtao/structure-jyeontu/tree/master/src/Heap
使用
目前我已经将代码上传到了 npm 上，大家可以直接npm install @jyeontu/structure-jyeontu进行安装，安装完成之后即可直接使用，如下：
const { MaxHeap } = require("@jyeontu/structure-jyeontu"); const list = [1, 3, 2, 4, 6, 3, 0, 9, 7]; const res = []; const myMaxHeap = new MaxHeap(list); while (myMaxHeap.front() != null) { res.push(myMaxHeap.pop()); } console.log(res); //[9, 7, 6, 4, 3, 3, 2, 1, 0]
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，在此谢谢大家的支持，我们下文再见 🙌。
