查找和最小的 K 对数字 · 交互式算法学习

1function kSmallestPairs(a, b, k) {2  if (!a.length || !b.length || !k) return [];3  const heap = [];4  const push = x => {5    heap.push(x);6    let i = heap.length - 1;7    while (i) {8      const p = (i - 1) >> 1;9      if (heap[p][0] <= heap[i][0]) break;10      [heap[p], heap[i]] = [heap[i], heap[p]];11      i = p12    }13  };14  const pop = () => {15    const top = heap[0],16      last = heap.pop();17    if (heap.length) {18      heap[0] = last;19      for (let i = 0;;) {20        let best = i,21          l = i * 2 + 1,22          r = l + 1;23        if (l < heap.length && heap[l][0] < heap[best][0]) best = l;24        if (r < heap.length && heap[r][0] < heap[best][0]) best = r;25        if (best === i) break;26        [heap[i], heap[best]] = [heap[best], heap[i]];27        i = best28      }29    }30    return top31  };32  for (let i = 0; i < Math.min(k, a.length); i++) push([a[i] + b[0], i, 0]);33  const out = [];34  while (k-- && heap.length) {35    const [, i, j] = pop();36    out.push([a[i], b[j]]);37    if (j + 1 < b.length) push([a[i] + b[j + 1], i, j + 1])38  }39  return out;40}