堆介绍

【学习 JavaScript 数据结构与算法（第 3 版）】第 11 章

堆数据结构

堆，也叫 二叉堆，是特殊的 二叉树，有 2 个特性：

1. 结构特性：是一棵 完全二叉树，表示树的第一层都有左右子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左子节点
2. 堆特性：不是最小堆就是最大堆

最大堆/大根堆/大顶堆

所有节点都 >= 每个它的子节点，可以快速导出树的最大值

最小堆/小根堆/小顶堆

所有节点都 <= 每个它的子节点，可以快速导出树的最小值

堆，并不一定是二叉搜索树（BST）

堆排序

最大堆可以得到一个升序的数组，最小堆可以得到一个降序的数组

用最大堆排序步骤：

1. 用数组创建一个最大堆
2. 将堆顶与堆尾（堆最后一个值）交换，将堆.legnth -1
3. 将剩下的元素不断重复 前 2 步，直到堆大小为 1

代码实现

自实现

class Heap {
  protected heap: number[]
  private isMin: boolean

  public constructor(type: string, array?: number[]) {
    this.heap = []
    this.isMin = type === 'min'

    if (array && array.length) {
      this.heapify(array)
    }
  }

  protected swap(i: number, j: number): void {
    const { heap } = this
    ;[heap[i], heap[j]] = [heap[j], heap[i]]
  }

  protected getParentIndex(i: number): number {
    return Math.floor((i - 1) / 2)
  }

  protected getLeftChildIndex(i: number): number {
    return i * 2 + 1
  }

  protected getRightChildIndex(i: number): number {
    return i * 2 + 2
  }

  //最后一个内部节点，有子节点的节点
  protected getLastHasChildIndex(): number {
    return Math.floor(this.getSize() / 2) - 1
  }

  //向上与父节点比较，找到合适位置
  protected siftUp(i: number): void {
    const { heap, getParentIndex, isMin } = this
    /**
     * 最小堆，当前节点 < 父节点，交换
     * 最大堆，当前节点 > 父节点，交换
     */
    while (
      i > 0 && isMin
        ? heap[i] < heap[getParentIndex(i)]
        : heap[i] > heap[getParentIndex(i)]
    ) {
      console.log('siftup i', i, heap[i], '父节点值', heap[getParentIndex(i)])

      const parentIdx = getParentIndex(i)
      this.swap(i, parentIdx)
      i = parentIdx
    }
  }

  //向下与左右子节点比较，找到合适位置
  protected siftDown(i: number): void {
    const { heap, isMin, getLeftChildIndex, getRightChildIndex } = this
    const size = this.getSize()
    let lci = getLeftChildIndex(i)
    const rci = getRightChildIndex(i)

    console.log(
      'siftdown i',
      i,
      '左子节点',
      'i',
      lci,
      '值',
      heap[lci],
      '右子节点',
      'i',
      rci,
      '值',
      heap[rci],
    )

    if (lci < size) {
      if (isMin) {
        // 比较左右子节点大小，找小
        if (rci < size && heap[rci] < heap[lci]) {
          lci = rci
        }
        // 如果 当前结点 < 较小者，不用再比较
        if (heap[i] <= heap[lci]) return
      } else {
        // 比较左右子节点大小，找大
        if (rci < size && heap[rci] > heap[lci]) {
          lci = rci
        }
        // 如果 当前结点 > 较大者，不用再比较
        if (heap[i] >= heap[lci]) return
      }

      console.log(i, lci)

      this.swap(i, lci)
      this.siftDown(lci)
    }
  }

  protected getTop(): number {
    if (this.getSize() === 0) {
      throw new Error('Failed to execute, Heap is Empty!')
    }
    return this.heap[0]
  }

  public add(val: number): void {
    // 先将新元素添加到尾部
    this.heap.push(val)
    // 再将该元素上浮到合适的位置
    this.siftUp(this.getSize() - 1)
  }

  public extract(): number {
    const top = this.getTop()
    // 交换堆顶和堆尾元素
    this.swap(0, this.getSize() - 1)
    // 将交换后的堆尾移出堆
    this.heap.pop()
    // 调整好堆
    this.siftDown(0)
    return top
  }

  public getSize(): number {
    return this.heap.length
  }

  public getAsArray(): number[] {
    return this.heap
  }

  public heapify(array?: number[]): number[] {
    if (array) {
      this.heap = array
    }

    const lastIndex = this.getLastHasChildIndex()
    for (let i = lastIndex; i >= 0; i--) {
      console.log(`------- 堆建 ${i} `)

      this.siftDown(i)

      console.log('堆建后', this.heap)
    }

    return this.heap
  }
}

class MinHeap extends Heap {
  public constructor(array?: number[]) {
    super('min', array)
  }

  public getMin(): number {
    return this.getTop()
  }
}

class MaxHeap extends Heap {
  public constructor(array?: number[]) {
    super('max', array)
  }

  public getMax(): number {
    return this.getTop()
  }
}

export const test = () => {
  console.log('👇 最小堆 ---------')

  const h = new MinHeap([0, 5, 1, 4, 10, -19, 100, 36, 19, 30])
  console.log('🌰 最小堆', h.getAsArray())
  console.log('🌰 最小值', h.getMin())
  console.log('🌰 extract', h.extract())
  console.log('🌰', h.getAsArray())
  h.add(-300)
  console.log('🌰 加 -300 后', h.getAsArray())

  console.log('👇 最大堆 -----------')

  const max = new MaxHeap([0, 5, 1, 4, 10, -19, 100, 36, 19])
  console.log('🌰 最大堆', max.getAsArray())
  console.log('🌰 最大值', max.getMax())
  console.log('🌰 extract', max.extract())
  console.log('🌰', max.getAsArray())
  max.add(-300)
  console.log('🌰 加 -300 后', max.getAsArray())
}

书的官方代码库

最小/大堆