⚡序言
我们都知道树是一个数据结构，但可能很少听到堆这个数据结构。其实，堆就是一种特殊的完全二叉树。而对于前端来说，我们通常了解最大堆和最小堆，也经常用最大堆和最小堆来解决各种问题。比如，数组中的第K个最大元素、文档中前K个高频元素等等。
在下面的这篇文章中，将讲解堆的基础知识，并手动地用 js 来构建一个最小堆，同时剖析几道经典的 leetcode 算法题。
接下来开始进入本文的讲解~🔥
🦘一、堆是什么？
- 堆是一种特殊的 完全二叉树 ，完全二叉树意味着每个节点都有两个孩子节点。
- 最大堆：所有的节点都 大于等于≥ 它的子节点；
- 最小堆：所有的节点都 小于等于≤ 它的子节点。
🐥二、JS中的堆
JS通常用数组来表示堆。- 左侧节点的位置是
2*index+1。 - 右侧节点的位置是
2*index+2。 - 父节点位置是
(index - 1) / 2。
🐝三、堆的应用
- 堆能够高效、快速地找出最大值和最小值，时间复杂度
O(1)。 - 在开发中，有时候我们可能会想要找到一个数组中的最大或者最小元素，而堆，就可以找出第K个最大（小）元素。
🐈四、构建一个最小堆
1. 定义
从上面的小知识中我们可以了解到，对于最小堆来说，它的所有节点都小于等于它的子节点。接下来我们来看堆这个数据结构的一些常见实现方法。
2. 方法
| 方法 | 含义 |
| swap() | 交换两个节点的位置 |
| getParentIndex() | 获取父节点的位置 |
| getLeftIndex() | 获取左侧子节点的位置 |
| getRightIndex() | 获取右侧子节点的位置 |
| shiftUp() | 进行上移操作 |
| shiftDown() | 进行下移操作 |
| insert() | 插入节点的值 |
| pop() | 删除堆顶操作 |
| peek() | 获取堆顶的值 |
| size() | 获取堆的大小 |
3. 用js代码实现最小堆
（1）初始化一个堆
首先我们需要先来定义一个空数组，这个数组用来存放一个堆。具体代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } } 复制代码
（2）交换位置swap()
初始化完一个堆之后，如果想要实现上下移操作，我们时不时的还需要对两个节点进行位置交换。那么我们再来写一个交换节点位置的方法。具体代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } } 复制代码
（3）获取父节点的位置getParentIndex()
上面我们讲到，父节点的位置是在 (index - 1) / 2 。 因此，我们需要传入当前节点的值索引 index ，来进行一个地板除操作，获取具体的父节点位置。具体代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取父节点的位置 getParentIndex(i){ return Math.floor((i - 1)/2); //也可以用以下这种右移操作的方法 //return (i - 1) >> 1; } } 复制代码
（4）获取左侧子节点的位置getLeftIndex()
对于左侧子节点来说，其索引为 2 * index + 1 ，也就是说，它是 当前节点的索引值的2倍 + 1 。具体实现代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取父节点的位置 getParentIndex(i){ return Math.floor((i - 1)/2); //也可以用以下这种右移操作的方法 //return (i - 1) >> 1; } //获取左侧子节点，i为当前节点的索引 getLeftIndex(i){ return i * 2 + 1; } } 复制代码
（5）获取右侧子节点的位置getRightIndex()
对于右侧子节点来说，其索引为 2 * index + 2 ，也就是说，它是 当前节点的索引值的2倍 + 2 。具体实现代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取父节点的位置 getParentIndex(i){ return Math.floor((i - 1)/2); //也可以用以下这种右移操作的方法 //return (i - 1) >> 1; } //获取左侧子节点，i为当前节点的索引 getLeftIndex(i){ return i * 2 + 1; } //获取右侧子节点，i为当前节点的索引 getRightIndex(i){ return i * 2 + 2; } } 复制代码
（6）进行上移操作shiftUp()
上面我们实现了获取父节点等获取各种索引的操作，现在，我们来实现上移操作。
对于上移操作来说，实现思路如下：
- 先判断当前节点的位置是否在堆的顶点处，如果是，则不进行上移操作；如果否，则继续进行比较；
- 获取父节点的位置索引，获取索引的目的是为了获取该索引的具体值；
- 将当前节点的值与父节点的值进行对比，如果父节点的值大于当前节点的值，则进行上移操作；
- 递归进行上移操作，直到到达堆顶为止。
下面给出具体的代码实现方法：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取父节点的位置 getParentIndex(i){ return Math.floor((i - 1)/2); //也可以用以下这种右移操作的方法 //return (i - 1) >> 1; } //shiftUp进行上移操作 shiftUp(index){ //如果在堆的顶点处，则不进行上移操作，直接返回结果 if(index === 0){ return; } //获取父节点(即获取当前节点的父节点的值，且每个节点的父节点只有一个) const parentIndex = this.getParentIndex(index); //判断如果堆的父节点如果大于子节点，则进行位置交换 if(this.heap[parentIndex] > this.heap[index]){ this.swap(parentIndex, index); //交换完成之后，继续递归进行上移操作 this.shinftUp(parentIndex); } } } 复制代码
（7）进行下移操作shiftDown()
对于下移操作来说，实现思路如下：
- 先获取左右侧节点；
- 将左侧子节点与当前节点进行比较，如果左侧子节点比当前节点小，则进行位置交换，之后将交换完的节点继续进行比较；
- 左侧节点比较完之后，接下来比较右侧节点；
- 将右侧子节点与当前节点进行比较，如果右侧子节点比当前节点小，则进行位置交换，之后将交换完的节点继续进行比较；
- 如此循环操作，直到最后一个节点为止。
下面给出具体的代码实现方法：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取左侧子节点，i为当前节点的索引 getLeftIndex(i){ return i * 2 + 1; } //获取右侧子节点，i为当前节点的索引 getRightIndex(i){ return i * 2 + 2; } // 进行下移操作 shiftDown(index){ // 获取左右侧子节点 const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); // 对左侧结点进行交换 if(this.heap[leftIndex] < this.heap[index]){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } // 对右侧结点进行交换 if(this.heap[rightIndex] < this.heap[index]){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } } 复制代码
（8）插入节点的值insert()
对于插入节点操作来说，实现思路如下：
- 将值插入堆的底部，即数组的尾部。
- 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值。
- 大小为k的堆中插入元素的时间复杂度为
O(logK)。
下面给出具体的代码实现方法：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取父节点的位置 getParentIndex(i){ return Math.floor((i - 1)/2); //也可以用以下这种右移操作的方法 //return (i - 1) >> 1; } //shiftUp进行上移操作 shiftUp(index){ //如果在堆的顶点处，则不进行上移操作，直接返回结果 if(index === 0){ return; } //获取父节点(即获取当前节点的父节点的值，且每个节点的父节点只有一个) const parentIndex = this.getParentIndex(index); //判断如果堆的父节点如果大于子节点，则进行位置交换 if(this.heap[parentIndex] > this.heap[index]){ this.swap(parentIndex, index); //交换完成之后，继续递归进行上移操作 this.shinftUp(parentIndex); } } //插入结点值的操作，value为被插入的值 insert(value){ //把新的值放到数组的最后一位 this.heap.push(value); //将值进行上移操作 this.shiftUp(this.heap.length - 1); } } 复制代码
（9）删除堆顶操作pop()
对于删除堆顶操作来说，实现思路如下：
- 用数组尾部元素替换堆顶（因为直接删除堆顶会破坏堆结构）。
- 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶。
- 大小为
k的堆中删除堆顶的时间复杂度为O(logK)。
下面给出具体的代码实现方法：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //交换节点i1和i2之间的位置 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } //获取左侧子节点，i为当前节点的索引 getLeftIndex(i){ return i * 2 + 1; } //获取右侧子节点，i为当前节点的索引 getRightIndex(i){ return i * 2 + 2; } // 进行下移操作 shiftDown(index){ // 获取左右侧子节点 const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); // 对左侧结点进行交换 if(this.heap[leftIndex] < this.heap[index]){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } // 对右侧结点进行交换 if(this.heap[rightIndex] < this.heap[index]){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } //删除堆顶操作 pop(){ //将尾部的值赋值给堆顶 this.heap[0] = this.heap.pop(); //进行下移操作 this.shiftDown(0); } } 复制代码
（10）获取堆顶的值peek()
对于获取堆顶的值操作来说，实现思路较为简单，也就是返回数组的头部即可获取堆顶的值。具体实现代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //获取堆顶的值 peek(){ return this.heap[0]; } } 复制代码
（11）获取堆的大小size()
对于获取堆的大小操作来说，实现思路其实就是获取整个堆的长度，也就是返回数组的长度。具体实现代码如下：
class MinHeap{ //创建一个构造器，存放一个堆 constructor(){ this.heap = []; } //获取堆的大小 size(){ return this.heap.length; } } 复制代码
（12）结果展示
完成上面的操作以后，接下来，我们来对写一组测试用例，演示具体的结果。具体代码如下：
const h = new MinHeap(); h.insert(3); h.insert(2); h.insert(1); h.pop(); console.log(h); // MinHeap { heap: [ 2, 4, 3 ] } h.peek(); h.size(); console.log(h.peek()); // 2 console.log(h.size()); // 3
