是什么

堆： 通常可以看着一棵完全二叉树的数组对象

分类

• 大顶堆
• 小顶堆

大顶堆

每个节点的值都大于子树的节点值

小顶堆

每个节点的值都小于子树的节点值

操作

• 插入
• 删除

插入

• 在数组尾部插入新值
• 上移操作，直到父节点小于这个新值

// 插入元素
insert(value) {
  this.heap.push(value)
  this.shifUp(this.heap.length - 1)
}

// 上移操作
shiftUp(index) {
  if (index === 0) { return }
  const parentIndex = this.getParentIndex(index)
  if(this.heap[parentIndex] > this.heap[index]){
    this.swap(parentIndex, index)
    this.shiftUp(parentIndex)
  }
}

删除

• 用数组尾部元素替换堆顶
• 下移操作，和子节点进行交换， 直到子节点大于新堆顶

// 删除元素
pop() {
  this.heap[0] = this.heap.pop()
  this.shiftDown(0)
}

// 下移操作
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)
  }
}

复杂度

Olog(n)