重学数据结构与算法-二叉堆

『22年09月19日』

斗西
图:斗西路口

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

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

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

二叉堆的常见操作

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

数据结构

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

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

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

example

对于给定位置 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);
     }
     }
  1. 插入算法
  • 如果是第一个元素,则直接插入
  • 如果已经不是第一个元素了,那么需要根据最小堆的规则(子节点必须永远大于等于父节点)调整二叉堆
    
    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);
      }
    }
  1. 移除最小值算法
  • 最小堆的最小值就是数组的第一个元素
  • 如果只有一个元素,则直接移除
  • 如果不止一个元素,移除后要重新组建二叉堆(堆化),堆化的规则如下:
    • 将最后一个元素移动到顶点
    • 从顶点开始重新调整堆

  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);
    }
    
  }
  
  
  1. 找到最小值
  • 最小值就是第一个元素,因为是最小堆
    
      findMinimum() {
        return this.heap[0];
      }
    

完整代码

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

二叉堆的应用

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