Why does this heap-based merge skip some values?

programming web dev
1

Hey everyone, I’m working on a small utility to merge several sorted arrays, and I’m using a min-heap so I don’t have to flatten everything first. It mostly works, but on duplicate values I sometimes lose items, which is worse than being a little slower.

function mergeSorted(lists) {
  const heap = [];
  const out = [];

  function push(node) {
    heap.push(node);
    heap.sort((a, b) => a.value - b.value);
  }

  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length) {
      push({ value: lists[i][0], list: i, index: 0 });
    }
  }

  while (heap.length) {
    const cur = heap.shift();
    out.push(cur.value);

    const nextIndex = cur.index + 1;
    if (lists[cur.list][nextIndex]) {
      push({ value: lists[cur.list][nextIndex], list: cur.list, index: nextIndex });
    }
  }

  return out;
}

console.log(mergeSorted([[1, 4, 4], [1, 3], [2, 4]]));

What am I overlooking here that makes some valid next values disappear when merging sorted arrays?

Hari :smiling_face_with_sunglasses:

2

You’re checking the next item by truthiness, not by whether that index exists.

So if (lists[cur.list][nextIndex]) will drop real values like 0 or "". The duplicate 4s aren’t the issue here. Change it to:


js
if (nextIndex < lists[cur.list].length) {
  push({ value: lists[cur.list][nextIndex], list: cur.list, index: nextIndex });
}

For your sample with [[1, 4, 4], [1, 3], [2, 4]], that should give [1, 1, 2, 3, 4, 4, 4].

Yoshiii