共计 5208 个字符，预计需要花费 14 分钟才能阅读完成。
这是第 90 篇不掺水的原创，想获取更多原创好文，请搜寻公众号关注咱们吧~ 本文首发于政采云前端博客：如何用 JS 实现二叉堆
如何用 JS 实现二叉堆
前言
二叉树 (Binary Tree) 是一种树形构造，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点、分支节点、叶子节点组成，如下图所示。每个分支节点也经常被称作为一棵子树，而二叉堆是一种非凡的树，它属于齐全二叉树。
二叉树与二叉堆的关系
在日常工作中会遇到很多数组的操作，比方排序等。那么了解二叉堆的实现对当前的开发效率会有所晋升，上面就简略介绍一下什么是二叉树，什么是二叉堆。
二叉树特色
- 根节点：二叉树最顶层的节点
- 分支节点：除了根节点以外且领有叶子节点
- 叶子节点：除了本身，没有其余子节点
在二叉树中，咱们经常还会用父节点和子节点来形容，比方上图中左侧节点 2 为 6 和 3 的父节点，反之 6 和 3 是 2 子节点。
二叉树分类
二叉树分为满二叉树 (full binary tree) 和齐全二叉树(complete binary tree)。
- 满二叉树：一棵深度为 k 且有 2 ^ k – 1 个节点的二叉树称为满二叉树
- 齐全二叉树：齐全二叉树是指最初一层右边是满的，左边可能满也可能不满，而后其余层都是满的二叉树称为齐全二叉树(满二叉树也是一种齐全二叉树)
二叉树构造
从图中咱们能够看出二叉树是从上到下顺次排列下来，可想而知能够用一个数组来示意二叉树的构造，从下标 index(0 – 8) 从上到下顺次排列。
- 二叉树左侧节点表达式 index * 2 + 1。例如：以根节点为例求左侧节点，根节点的下标为 0，则左侧节点的序数是 1，对应数组中的值为 1
- 二叉树右侧节点表达式 index * 2 + 2。例如：以根节点为例求右侧节点，根节点的下标为 0，则右侧节点的序数是 2，对应数组中的值为 8
- 二叉树叶子节点表达式 序数 >= floor(N / 2)都是叶子节点（N 是数组的长度）。例如：floor(9 / 2) = 4，则从下标 4 开始的值都为叶子节点
二叉堆特色
二叉堆是一个齐全二叉树，父节点与子节点要放弃固定的序关系，并且每个节点的左子树和右子树都是一个二叉堆。
从上图能够看出
- 图一：每个父节点大于子节点或等于子节点，满足二叉堆的性质
- 图二：其中有一个父节点小于子节点则不满足二叉堆性质
二叉堆分类
二叉堆依据排序不同，能够分为最大堆和最小堆
- 最大堆：根节点的键值是所有堆节点键值中最大者，且每个父节点的值都比子节点的值大
- 最小堆：根节点的键值是所有堆节点键值中最小者，且每个父节点的值都比子节点的值小
如何实现二叉堆
通过下面的讲述想必大家对二叉堆有了肯定的了解，那么接下来就是如何实现。以最大堆为例，首先要初始化数组而后通过替换地位造成最大堆。
初始化二叉堆
从下面形容，咱们能够晓得二叉堆其实就是一个数组，那么初始化就非常简单了。
class Heap{constructor(arr){this.data = [...arr];
this.size = this.data.length;
}
}父子节点替换地位
图一中 2 作为父节点小于子节点，很显然不合乎最大堆性质。maxHeapify 函数能够把每个不合乎最大堆性质的节点调换地位，从而满足最大堆性质的数组。
调整步骤：
1. 调整分支节点 2 的地位（不满足最大堆性质）
2. 获取父节点 2 的左右节点 (12 , 5)，从 (2 , 15 , 5) 中进行比拟
3. 找出最大的节点与父节点进行替换，如果该节点自身为最大节点则进行操作
4. 反复 step2 的操作，从 2 , 4 , 7 中找出最大值与 2 做替换（递归）
maxHeapify(i) {
let max = i;
if(i >= this.size){return;}
// 以后序号的左节点
const l = i * 2 + 1;
// 以后须要的右节点
const r = i * 2 + 2;
// 求以后节点与其左右节点三者中的最大值
if(l < this.size && this.data[l] > this.data[max]){max = l;}
if(r < this.size && this.data[r] > this.data[max]){max = r;}
// 最终 max 节点是其自身, 则曾经满足最大堆性质，进行操作
if(max === i) {return;}
// 父节点与最大值节点做替换
const t = this.data[i];
this.data[i] = this.data[max];
this.data[max] = t;
// 递归向下继续执行
return this.maxHeapify(max);
}造成最大堆
咱们能够看到，初始化是由一个数组组成，以下图为例很显然并不会满足最大堆的性质，上述 maxHeapify 函数只是对某一个节点作出对调，无奈对整个数组进行重构，所以咱们要顺次对数组进行递归重构。
1. 找到所有分支节点 Math.floor(N / 2)（不包含叶子节点）
2. 将找到的子节点进行 maxHeapify 操作
rebuildHeap(){
// 叶子节点
const L = Math.floor(this.size / 2);
for(let i = L - 1; i >= 0; i--){this.maxHeapify(i);
}
}生成一个升序的数组
1.swap 函数替换首位地位
2. 将最初一个从堆中拿出相当于 size – 1
3. 执行 maxHeapify 函数进行根节点比拟找出最大值进行替换
4. 最终 data 会变成一个升序的数组
sort() {for(let i = this.size - 1; i > 0; i--){swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}插入方法
Insert 函数作为插入节点函数，首先
1. 往 data 结尾插入节点
2. 因为节点追加，size + 1
3. 因为一个父节点领有 2 个子节点，咱们能够依据这个性质通过 isHeap 函数获取第一个叶子节点，能够通过第一个叶子节点获取新插入的节点，而后进行 3 个值的比照，找出最大值，判断插入的节点。如果跟父节点雷同则不进行重构（相等满足二叉堆性质），否则进行 rebuildHeap 重构堆
isHeap() {const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {return false;}
return true;
}
}
insert(key) {this.data[this.size] = key;
this.size++
if (this.isHeap()) {return;}
this.rebuildHeap();}删除办法
delete 函数作为删除节点，首先
1. 删除传入 index 的节点
2. 因为节点删除，size – 1
3. 反复下面插入节点的操作
delete(index) {if (index >= this.size) {return;}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {return;}
this.rebuildHeap();}残缺代码
/**
* 最大堆
*/
function left(i) {return (i * 2) + 1;
}
function right(i) {return (i * 2) + 2;
}
function swap(A, i, j) {const t = A[i];
A[i] = A[j];
A[j] = t;
}
class Heap {constructor(arr) {this.data = [...arr];
this.size = this.data.length;
this.rebuildHeap = this.rebuildHeap.bind(this);
this.isHeap = this.isHeap.bind(this);
this.sort = this.sort.bind(this);
this.insert = this.insert.bind(this);
this.delete = this.delete.bind(this);
this.maxHeapify = this.maxHeapify.bind(this);
}
/**
* 重构堆，造成最大堆
*/
rebuildHeap() {const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {this.maxHeapify(i);
}
}
isHeap() {const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {return false;}
return true;
}
}
sort() {for (let i = this.size - 1; i > 0; i--) {swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
insert(key) {this.data[this.size++] = key;
if (this.isHeap()) {return;}
this.rebuildHeap();}
delete(index) {if (index >= this.size) {return;}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {return;}
this.rebuildHeap();}
/**
* 替换父子节点地位，合乎最大堆特色
* @param {*} i
*/
maxHeapify(i) {
let max = i;
if (i >= this.size) {return;}
// 求左右节点中较大的序号
const l = left(i);
const r = right(i);
if (l < this.size && this.data[l] > this.data[max]) {max = l;}
if (r < this.size && this.data[r] > this.data[max]) {max = r;}
// 如果以后节点最大，曾经是最大堆
if (max === i) {return;}
swap(this.data, i, max);
// 递归向下继续执行
return this.maxHeapify(max);
}
}
module.exports = Heap;示例
置信通过下面的讲述大家对最大堆的实现曾经有了肯定的了解，咱们能够利用这个来进行排序。
const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7];
const fun = new Heap(arr);
fun.rebuildHeap(); // 造成最大堆的构造
fun.sort();// 通过排序，生成一个升序的数组
console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15]总结
文章中次要讲述了二叉树、二叉堆的概念，而后通过代码实现二叉堆。咱们能够通过二叉堆来做排序和优先级队列等。
举荐浏览
前端异样的捕捉与解决
编写高质量可保护的代码：组件的形象与粒度
招贤纳士
政采云前端团队（ZooTeam），一个年老富裕激情和创造力的前端团队，隶属于政采云产品研发部，Base 在风景如画的杭州。团队现有 40 余个前端小伙伴，平均年龄 27 岁，近 3 成是全栈工程师，妥妥的青年风暴团。成员形成既有来自于阿里、网易的“老”兵，也有浙大、中科大、杭电等校的应届新人。团队在日常的业务对接之外，还在物料体系、工程平台、搭建平台、性能体验、云端利用、数据分析及可视化等方向进行技术摸索和实战，推动并落地了一系列的外部技术产品，继续摸索前端技术体系的新边界。
如果你想扭转始终被事折腾，心愿开始能折腾事；如果你想扭转始终被告诫须要多些想法，却无从破局；如果你想扭转你有能力去做成那个后果，却不须要你；如果你想扭转你想做成的事须要一个团队去撑持，但没你带人的地位；如果你想扭转既定的节奏，将会是“5 年工作工夫 3 年工作教训”；如果你想扭转原本悟性不错，但总是有那一层窗户纸的含糊… 如果你置信置信的力量，置信平凡人能成就不凡事，置信能遇到更好的本人。如果你心愿参加到随着业务腾飞的过程，亲手推动一个有着深刻的业务了解、欠缺的技术体系、技术发明价值、影响力外溢的前端团队的成长历程，我感觉咱们该聊聊。任何工夫，等着你写点什么，发给 ZooTeam@cai-inc.com