二叉堆的概念与实现

[ChuChencheng]

概念

本质上是完全二叉树

分为两种类型

1. 最大堆：父节点的值大于或等于子节点
2. 最小堆：父节点的值小于或等于子节点

特性

堆内部能实现自我调整，对于二叉堆有以下操作：

1. 构建二叉堆
2. 插入节点
3. 删除节点

插入节点

当插入一个节点到二叉堆中，首先将节点插入到二叉堆的末尾，然后进行“上浮”操作
从末尾节点开始，与其父节点进行比较，以最小堆为例，如果插入的节点小于父节点，则与父节点的位置进行交换，重复该步骤，直到节点到达合适的位置，即大于或等于其父节点

删除节点

当要从二叉堆中删除节点，将堆顶（即二叉树根节点）元素删除，然后将末尾的元素移动到堆顶
这时堆顶元素的位置不一定是正确的，需要做一个“下沉”操作
从堆顶元素开始，与其左右子节点进行比较，如果当前节点比左右子节点大，则与最小的子节点进行交换，直到节点到达合适的位置，即节点小于或等于其左右子节点

构建二叉堆

初始化二叉堆，可以看成是把一个无序的二叉堆调整为有序的二叉堆的过程，只需要对于所有非子节点进行“下沉”操作，即可生成一个有序的二叉堆

数据结构

二叉堆的存储结构不用链表，而是可以直接用一个数组来存储。
其中，第一个元素即为堆顶
对于节点 n 来说，
其左子节点的索引为 2 * n + 1
右子节点索引为 2 * n + 2
父节点索引为 Math.floor((n - 1) / 2)

二叉堆的最后一个非叶子节点的索引为 Math.floor((length - 2) / 2)

实现

/** 最小堆 */
class BinaryHeap {
  private heap: number[] = []

  constructor (elements: number[]) {
    this.heap = elements
    // 构建二叉堆，对每个非叶子节点进行“下沉”操作
    for (let i = Math.floor((this.heap.length - 2) / 2); i >= 0; i--) {
      this.down(i)
    }
  }

  /** 插入 */
  insert (value: number) {
    this.heap.push(value)
    this.up()
  }

  /** 删除 */
  delete () {
    this.heap.shift()
    const last = this.heap.pop()
    if (last != null) {
      this.heap.unshift(last)
      this.down()
    }
  }

  /** 上浮 */
  up () {
    let n = this.heap.length - 1
    if (n <= 0) return
    const target = this.heap[n]
    let parentIndex = Math.floor((n - 1) / 2)
    // 如果父节点大于子节点，则将父节点复制到子节点的位置，当前父节点的位置可以复制为上浮节点的值，但是还需要继续往上寻找目标位置，所以可以先不用赋值，等循环结束后再在目标位置赋值为上浮的节点；然后继续往上寻找，直到不符合条件，即找到了上浮节点的目标位置
    while (parentIndex > 0 && this.heap[parentIndex] > target) {
      this.heap[n] = this.heap[parentIndex]
      n = parentIndex
      parentIndex = Math.floor((n - 1) / 2)
    }
    this.heap[n] = target
  }

  /** 下沉 */
  down (n: number = 0) {
    const target = this.heap[n]
    let parentIndex = n
    let leftChildIndex = 2 * n + 1
    const length = this.heap.length
    while (leftChildIndex < length) {
      // 这里定义最小的子节点，可以直接用 leftChildIndex ，为了方便阅读，多定义一个变量
      let minChildIndex = leftChildIndex
      const rightChildIndex = leftChildIndex + 1
      if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[leftChildIndex]) {
        minChildIndex = rightChildIndex
      }
      // 如果最小的子节点都大于待下沉的节点，说明下沉节点已经到达目标位置
      if (this.heap[minChildIndex] >= target) break
      // 否则将最小子节点的值复制到它的父节点上，下沉节点的值最后循环退出后再复制到目标位置
      this.heap[parentIndex] = this.heap[minChildIndex]
      parentIndex = minChildIndex
      leftChildIndex = 2 * parentIndex + 1
    }
    this.heap[parentIndex] = target
  }
}

参考

漫画：什么是二叉堆？