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

最大堆

• 完全二叉树：从上到下，从左到右，编号为 i 的节点与满二叉树编号为 i 的节点位置一致
• 大根堆：根节点的值大于或等于子节点的值

代码

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

  swap (a, b) {
    const tmp = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = 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), 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 top = this.top()
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }

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

测试

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