图：斗西路口

二叉堆是一种特殊的二叉树，具有以下两个特性：

• 结构特性
  它是一颗完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点
• 堆特性
  不是最大堆就是最小堆。所有节点都大于等于（最大堆）或者小于等于（最小堆）它的左右子节点

下图展示了一些合法的二叉堆：

二叉堆的常见操作

• insert(value): 插入一个新节点
• extract(): 移除顶点，并返回顶点值
• findMininum(): 返回最小/大值，但不移除这个值

数据结构

怎么用 JavaScript 定义最小堆的数据结构？

通常，二叉树节点数据存储可以用链表也可以用数组，一般完全二叉树适合用数组来表示，因为这样就不需要存储子节点的指针，这样就可以节省存储空间，直接可以通过数组元素的位置计算出子节点的位置；其他类型的二叉树则不建议用数组来实现，因为并不是所有节点都遵循从左往右排列，所以节点的左右节点就容易为空，而造成数组空洞

所以可以用数组的方式来存储一颗完全二叉树，而节点之间有这个的关系：

对于给定位置 index 的节点：

• 它的左子节点位置为 2 x index +1
• 它的右子节点位置为 2 x index +2
• 它的父节点位置为（index-1）/ 2 向下取整

所以可以根据这个特性来构建二叉堆，以下以最小堆为例子：

1. 用数组来存储节点

   
   class MinHeap {
    constructor() {
        this.heap = [];
    }
    size() {
        return this.heap.length;
    }
   
    leftChild(index) {
        return 2 * index + 1;
    }
   
    rightChild(index) {
        return 2 * index + 2;
    }
   
    parent(index) {
        return Math.floor((index - 1) / 2);
    }
    }

2. 插入算法

• 如果是第一个元素，则直接插入
• 如果已经不是第一个元素了，那么需要根据最小堆的规则（子节点必须永远大于等于父节点）调整二叉堆

  
  insert(val) {
    if (this.size() === 0) {
      this.heap.push(val);
    } else {
      this.heap.push(val);
      this.siftUp(this.heap.length - 1);
    }
  }
  
  siftUp(index) {
    let parent = this.parent(index);
    while (this.heap[parent] > this.heap[index]) {
      const temp = this.heap[parent];
      this.heap[parent] = this.heap[index];
      this.heap[index] = temp;
      index = parent;
      parent = this.parent(parent);
    }
  }

3. 移除最小值算法

• 最小堆的最小值就是数组的第一个元素
• 如果只有一个元素，则直接移除
• 如果不止一个元素，移除后要重新组建二叉堆（堆化），堆化的规则如下：
  • 将最后一个元素移动到顶点
  • 从顶点开始重新调整堆

  extract() {
    // shift with an empty array will return undefined
   if (this.size() <= 2) {
      return this.heap.shift();
    } else {
      const result = this.heap[0];
      //  将最后一个元素移动顶点
      this.heap[0] = this.heap.pop();
      this.siftDown(0);
      return result;
    }
  }
  siftDown(index) {
    let leftChild = this.leftChild(index);
    let rightChild = this.rightChild(index);
    if (leftChild >= this.size()) return;
    let current = index;
    // 找到子树的最小节点并替换
    if (typeof this.heap[leftChild] !== undefined &&
      this.heap[current] > this.heap[leftChild]) {
      current = leftChild;
    }
    if (typeof this.heap[rightChild] !== undefined &&
      this.heap[current] > this.heap[rightChild]) {
      current = rightChild;
    }
    // 如果没有比顶点小的节点了，那就可停止堆化操作了
    if (current !== index) {
      const temp = this.heap[index];
      this.heap[index] = this.heap[current];
      this.heap[current] = temp;
      this.siftDown(current);
    }
    
  }
  
  

4. 找到最小值

• 最小值就是第一个元素，因为是最小堆

  
    findMinimum() {
      return this.heap[0];
    }
  

完整代码

See the Pen MinHeap by JinZhang (@jackzong) on CodePen.

二叉堆的应用

• 实现优先队列
  比如，React 在其 scheduler 上的调度实现就是用了最小堆 React 源码
• 堆排序算法 链接