advanced

Review: the sift that only looks left

This is recall. The code looks finished and is wrong. Find the defect and fix it. You are graded on tests you cannot see.

The job runner picks work off a min-heap of priorities. The heap below is a correct-looking array implementation — sift-up is right, pop swaps in the last leaf, everything indexes cleanly. Its tests pass.

export class MinHeap {
  #values: number[] = []

  get size(): number {
    return this.#values.length
  }

  peek(): number | undefined {
    return this.#values[0]
  }

  push(value: number): void {
    this.#values.push(value)
    let index = this.#values.length - 1
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      const current = this.#values[index] as number
      const parent = this.#values[parentIndex] as number
      if (current >= parent) break
      this.#values[index] = parent
      this.#values[parentIndex] = current
      index = parentIndex
    }
  }

  pop(): number | undefined {
    if (this.#values.length === 0) return undefined
    const top = this.#values[0] as number
    const last = this.#values.pop() as number
    if (this.#values.length > 0) {
      this.#values[0] = last
      this.#siftDown(0)
    }
    return top
  }

  #siftDown(index: number): void {
    for (;;) {
      const left = 2 * index + 1
      if (left >= this.#values.length) break
      const current = this.#values[index] as number
      const leftChild = this.#values[left] as number
      if (leftChild >= current) break
      this.#values[index] = leftChild
      this.#values[left] = current
      index = left
    }
  }
}

review — find the defectCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code