Method siftDown

common/src/util/min-heap.ts:36–63

(index: number)

  }

  private siftDown(index: number): void {
    while (true) {
      let minIndex = index
      const leftChild = this.getLeftChildIndex(index)
      const rightChild = this.getRightChildIndex(index)

      if (
        leftChild < this.heap.length &&
        this.heap[leftChild].score < this.heap[minIndex].score
      ) {
        minIndex = leftChild
      }

      if (
        rightChild < this.heap.length &&
        this.heap[rightChild].score < this.heap[minIndex].score
      ) {
        minIndex = rightChild
      }

      if (minIndex === index) {
        break
      }

      this.swap(index, minIndex)
      index = minIndex
    }
  }

  insert(item: T, score: number): void {
    this.heap.push({ item, score })