⚡序言

我们都知道树是一个数据结构，但可能很少听到堆这个数据结构。其实，堆就是一种特殊的完全二叉树。而对于前端来说，我们通常了解最大堆和最小堆，也经常用最大堆和最小堆来解决各种问题。比如，数组中的第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

最小堆最大堆了解吗？一文了解堆在前端中的应用(一）

⚡序言

🦘一、堆是什么？

🐥二、JS中的堆

🐝三、堆的应用

🐈四、构建一个最小堆

1. 定义

2. 方法

3. 用js代码实现最小堆

（1）初始化一个堆

（2）交换位置swap()

（3）获取父节点的位置getParentIndex()

（4）获取左侧子节点的位置getLeftIndex()

（5）获取右侧子节点的位置getRightIndex()

（6）进行上移操作shiftUp()

（7）进行下移操作shiftDown()

（8）插入节点的值insert()

（9）删除堆顶操作pop()

（10）获取堆顶的值peek()

（11）获取堆的大小size()

（12）结果展示

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

最小堆最大堆了解吗？一文了解堆在前端中的应用(一）

⚡序言

🦘一、堆是什么？

🐥二、JS中的堆

🐝三、堆的应用

🐈四、构建一个最小堆

1. 定义

2. 方法

3. 用js代码实现最小堆

（1）初始化一个堆

（2）交换位置swap()

（3）获取父节点的位置getParentIndex()

（4）获取左侧子节点的位置getLeftIndex()

（5）获取右侧子节点的位置getRightIndex()

（6）进行上移操作shiftUp()

（7）进行下移操作shiftDown()

（8）插入节点的值insert()

（9）删除堆顶操作pop()

（10）获取堆顶的值peek()

（11）获取堆的大小size()

（12）结果展示

热门文章

最新文章

相关课程

相关电子书

相关实验场景