二叉堆

[YBFACC]

二叉堆

可以实现大顶堆或者小顶堆。

可以便利的解决一类 topK 问题。

215. 数组中的第K个最大元素

可视化工具

以小顶堆为例：

• 根节点小于所有子节点

• 用列表来模拟树的结构

  • 得知子节点的序号index，求父节点Math.floor((index - 1) / 2)
  • 得知父节点的序号index，求左子节点index*2+1，求右节点index*2+2

• 插入：节点放在数组末尾

  • 插入后与父节点进行比较

    • 若父节点小于子节点，进行交换

  • 重复该操作，直到父节点比子节点小

• 弹出根节点

  • 将根节点与数组最后一位进行交换

  • 然后pop（）弹出当前堆的最小值

  • 进行重建

    • 左右子节点选出最小数

    • 与根节点进行比较

      • 根节点>最小数,交换节点，递归重建

      • 根节点<最小数,结束

插入

弹出

代码

function swap(arr, i, j) {
  ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

class MinHeap {
  constructor(arr = []) {
    this.container = []
    if (Array.isArray(arr)) {
      arr.forEach(this.insert.bind(this))
    }
  }

  insert(data) {
    const { container } = this

    container.push(data)
    let index = container.length - 1
    while (index) {
      let parent = Math.floor((index - 1) / 2)
      if (container[index] >= container[parent]) {
        break
      }
      swap(container, index, parent)
      index = parent
    }
  }

  extract() {
    const { container } = this
    if (!container.length) {
      return null
    }

    swap(container, 0, container.length - 1)
    const res = container.pop()
    const length = container.length
    let index = 0,
      exchange = index * 2 + 1

    while (exchange < length) {
      let right = index * 2 + 2
      if (right < length && container[right] < container[exchange]) {
        exchange = right
      }
      if (container[exchange] >= container[index]) {
        break
      }
      swap(container, exchange, index)
      index = exchange
      exchange = index * 2 + 1
    }

    return res
  }

  top() {
    if (this.container.length) return this.container[0]
    return null
  }
}

function getMin(arr) {
  const heap = new MinHeap(arr.slice())
  for (let i = 0; i < arr.length; ++i) {
    console.log(heap.extract())
  }
}

getMin([4, 5, 8, 2, 1, 10, 11, 5, 7, 9, 5, 7])