堆

堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。

堆存储数据是用一个一维数组存取，堆的每个节点的左边子节点索引是 i * 2 + 1，右边是 i * 2 + 2，父节点是 (i - 1) /2，i为当前节点在 head 数组中的索引

堆操作

操作	描述
build	创建一个空堆
insert	向堆中插入一个新元素
update	将新元素提升使其符合堆的性质
get	获取当前堆顶元素的值
delete	删除堆顶元素
heapify	使删除堆顶元素的堆再次成为堆

代码实现（最小堆）

// 堆的每个节点的左边子节点索引是 i * 2 + 1，右边是 i * 2 + 2，父节点是 (i - 1) /2。i 为当前节点在head中的索引
class MinHeap {
  constructor() {
    this.heap = []
  }

  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1)
  }

  // 删除最小元素
  deleteMin() {
    return this.delete(0)
  }
  // 删除任意元素
  delete(i) {
    // 交换首位元素
    const lastIndex = this.heap.length - 1
    if (lastIndex < i) return
    const r = this.heap[i]
    this.heap[i] = this.heap[lastIndex]
    this.heap[lastIndex] = r
    this.heap.splice(lastIndex, 1)
    this.shiftDown(i)
    this.shiftUp(i)
    return r
  }

  /**
   * 子节点和父节点交换，从子级遍历到父级
   * @param {*} i
   */
  shiftUp(i) {
    // 获取父级的下标
    let parentIndex = parseInt((i - 1) / 2)

    // 最大堆和最小堆，通过这里的比较运算符设置
    while (this.heap[i] < this.heap[parentIndex]) {
      const temp = this.heap[i]
      this.heap[i] = this.heap[parentIndex]
      this.heap[parentIndex] = temp
      i = parentIndex
      parentIndex = parseInt((i - 1) / 2)
    }
  }

  /**
   * 把最小值放到最顶端
   * 父节点和子节点交换，从父级遍历到子级
   * @param {*} i
   */
  shiftDown(i) {
    const size = this.heap.length - 1
    while (true) {
      let lChildIndex = i * 2 + 1
      let rChildIndex = i * 2 + 2
      const isSwapLeft = lChildIndex <= size  && this.heap[i] > this.heap[lChildIndex]
      const isSwapRight = rChildIndex <= size  && this.heap[i] > this.heap[rChildIndex]

      if (isSwapLeft) {
        const temp = this.heap[i]
        this.heap[i] = this.heap[lChildIndex]
        this.heap[lChildIndex] = temp
        i = lChildIndex
        continue
      } else if (isSwapRight) {
        const temp = this.heap[i]
        this.heap[i] = this.heap[rChildIndex]
        this.heap[rChildIndex] = temp
        i = rChildIndex
      }
      break
    }
  }
}

const h = new MinHeap()

h.insert(1)
h.insert(4)
h.insert(2)
h.insert(5)
h.insert(6)
h.insert(7)
h.insert(3)
// h.insert(81)
console.log(h.heap)
h.delete(3)
console.log(h.heap)