JavaScript 最小堆（小根堆、小顶堆）代码

最小堆，又称为小根堆，小顶堆，实现 JavaScript 版小根堆的代码。

最小堆

• 完全二叉树：节点按从上到下，从左到右编号，编号为 i 的节点与满二叉树中编号为 i 的节点位置相同
• 小根堆：根节点的值总是 <= 叶子节点的值

代码

class MinHeap {
  constructor() {
    this.heap = []
    this.size = 0
  }

  swap(i, j) {
    const tmp = this.heap[i]
    this.heap[i] = this.heap[j]
    this.heap[j] = tmp
  }

  getParentIndex(index) {
    return index - 1 >> 1
  }

  shiftUp(index) {
    const parentIndex = this.getParentIndex(index)
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  getLeftIndex(index) {
    return (index << 1) + 1
  }

  getRightIndex(index) {
    return (index << 1) + 2
  }

  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

  push(value) {
    this.heap.push(value)
    this.shiftUp(this.size++)
  }

  top() {
    return this.heap[0]
  }

  pop() {
    if (this.size === 0) return null
    if (--this.size === 0) return this.heap.pop()
    const tmp = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return tmp
  }

  isEmpty() {
    return this.size === 0
  }
}

测试

const minHeap = new MinHeap()
for (const a of [3,5,2,4,1]) minHeap.push(a)
while (!minHeap.isEmpty()) console.log(minHeap.pop())
// [1, 2, 3, 4, 5]