Why does this heap-based scheduler skip a task after I reinsert it?

programming web dev
1

Hey folks, I’m working on a little task scheduler in TypeScript for practice, and I’m trying to use a min-heap so I can always grab the next task by time. The weird part is when I pop one task, update its time, and push it back, another task sometimes gets skipped, which makes me think I broke the heap while trying to keep it fast.

class MinHeap {
  data: { id: string; time: number }[] = [];

  push(item: { id: string; time: number }) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const end = this.data.pop()!;
    if (this.data.length) {
      this.data[0] = end;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(i: number) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p].time <= this.data[i].time) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }

  bubbleDown(i: number) {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const left = i * 2 + 1;
      const right = i * 2 + 2;

      if (left < n && this.data[left].time < this.data[smallest].time) {
        smallest = left;
      }
      if (right < n && this.data[right].time < this.data[smallest].time) {
        smallest = right;
      }
      if (smallest === i) break;

      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
    }
  }
}

const heap = new MinHeap();
heap.push({ id: "a", time: 2 });
heap.push({ id: "b", time: 5 });
heap.push({ id: "c", time: 3 });

const task = heap.pop()!;
task.time = 10;
heap.push(task);

console.log(heap.data);

Am I missing something obvious in my heap maintenance here, or is reinserting a mutated item the part that’s biting me?

Yoshiii :grinning_face:

2

Your bubbleDown is currently doing only one downward move, not fully restoring the heap after pop() puts the last item at the root.

Reinserting the updated task is fine because that task is already out of the heap. The real bug is that after swapping with the smaller child, you need to keep going from that child index. If you stop early, the heap property is still broken lower down, so later pops can look like a task got skipped.

The smallest fix is this:

// keep sinking after each swap
i = smallest;
bubbleDown(i: number) {
  const n = this.data.length;

  while (true) {
    let smallest = i;
    const left = i * 2 + 1;
    const right = i * 2 + 2;

    if (left < n && this.data[left].time < this.data[smallest].time) {
      smallest = left;
    }
    if (right < n && this.data[right].time < this.data[smallest].time) {
      smallest = right;
    }
    if (smallest === i) break;

    [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
    i = smallest;
  }
}

That i = smallest line is the whole issue here.

  • The swap moves the too-large item down one level.
  • i = smallest ensures that same item keeps sinking until its subtree is valid too.

That restores the heap all the way down instead of only fixing the top swap.

Here’s a tiny runnable check with your task.time = 10 flow:

class MinHeap {
  data: { id: string; time: number }[] = [];

  push(item: { id: string; time: number }) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;

    const top = this.data[0];
    const end = this.data.pop()!;

    if (this.data.length) {
      this.data[0] = end;
      this.bubbleDown(0);
    }

    return top;
  }

  bubbleUp(i: number) {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.data[p].time <= this.data[i].time) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }

  bubbleDown(i: number) {
    const n = this.data.length;

    while (true) {
      let smallest = i;
      const left = i * 2 + 1;
      const right = i * 2 + 2;

      if (left < n && this.data[left].time < this.data[smallest].time) {
        smallest = left;
      }
      if (right < n && this.data[right].time < this.data[smallest].time) {
        smallest = right;
      }
      if (smallest === i) break;

      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

const heap = new MinHeap();
heap.push({ id: "a", time: 2 });
heap.push({ id: "b", time: 5 });
heap.push({ id: "c", time: 3 });

const task = heap.pop()!;
task.time = 10;
heap.push(task);

console.log(heap.pop()); // { id: "c", time: 3 }
console.log(heap.pop()); // { id: "b", time: 5 }
console.log(heap.pop()); // { id: "a", time: 10 }

If you ever mutate an item while it is still inside this.data, reheapify after that too.

BayMax

3

@Baymax called out the missing i = smallest, and the other practical gotcha is mutating an item while it still lives in this.data because that silently invalidates the heap unless you support decreaseKey or reheapify that index.

Ellen

4

@Ellen1979 your “mutating an item while it still lives in this.data” note is the sneaky one, because object references make that bug feel random.

Yoshiii