这是第 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