[Heap] Find K Pairs with Smallest Sums

373. Find K Pairs with Smallest Sums

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다. nums1과 nums2가 각각 1만개 데이터인 테스트 케이스에서 런타임 에러 terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc가 발생하였습니다. 즉, 필자는 제출 환경에서 제한하는 시간 복잡도를 초과하였습니다.

function Heap() {
  this.arr = [];  
}

Heap.prototype.swap = function (a, b) {
  const temp = this.arr[a];
  this.arr[a] = this.arr[b];
  this.arr[b] = temp;
}

Heap.prototype.getSum = function(i) {  
  return this.arr[i][0] + this.arr[i][1];
}

Heap.prototype.push = function (e) {
  this.arr[this.arr.length] = e;
  this.bubbleUp(this.arr.length - 1);  
}

Heap.prototype.bubbleUp = function(i) {
  const child = i;
  const parent = Math.floor((i - 1) / 2);

  if(parent >= 0 && this.getSum(child) < this.getSum(parent)) {
    this.swap(child, parent);   
    this.bubbleUp(parent);
  }
}

Heap.prototype.pop = function() {
  const max = this.arr[0];
  this.arr[0] = this.arr[this.arr.length - 1];

  this.arr.pop();
  this.bubbleDown(0);

  return max;
}

Heap.prototype.bubbleDown = function(i) {
  let child = 2 * i + 1;
  const rightChild = 2 * i + 2;

  if(child <= this.arr.length - 1) {
    if(
      rightChild <= this.arr.length - 1 
      && this.getSum(child) > this.getSum(rightChild)
    ) {
      child = rightChild;
    }

    if(this.getSum(i) > this.getSum(child)) {
      this.swap(i, child);
      this.bubbleDown(child);
    }
  }
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */
var kSmallestPairs = function(nums1, nums2, k) {
  const heap = new Heap();  

  for(const each of nums1) {
    for(const other of nums2) {
      heap.push([each, other])
    }
  }
  
  const ans = [];

  for(let i = 0; i < k; i++) {
    const e = heap.pop();

    if(!e) {
      continue;
    }

    ans.push(e);    
  }

  return ans;
};

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using min heap with less push time

해답의 전문은 링크를 확인해주세요.

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this._bubbleUp();
    }

    pop() {
        if (this.size() === 1) return this.heap.pop();
        const smallest = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._sinkDown(0);
        return smallest;
    }

    size() {
        return this.heap.length;
    }

    _bubbleUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[parentIndex][0] > this.heap[index][0]) {
                [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    _sinkDown(index) {
        const left = 2 * index + 1;
        const right = 2 * index + 2;
        let smallest = index;

        if (left < this.size() && this.heap[smallest][0] > this.heap[left][0]) {
            smallest = left;
        }

        if (right < this.size() && this.heap[smallest][0] > this.heap[right][0]) {
            smallest = right;
        }

        if (smallest !== index) {
            [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
            this._sinkDown(smallest);
        }
    }
}

var kSmallestPairs = function(nums1, nums2, k) {
    const heap = new MinHeap();
    const result = [];
    
    if (nums1.length === 0 || nums2.length === 0) return [];

    for (let i = 0; i < Math.min(k, nums1.length); i++) {
        heap.push([nums1[i] + nums2[0], i, 0]);
    }

    while (k > 0 && heap.size() > 0) {
        const [val, i, j] = heap.pop();
        result.push([nums1[i], nums2[j]]);
        k--;

        if (j + 1 < nums2.length) {
            heap.push([nums1[i] + nums2[j + 1], i, j + 1]);
        }
    }

    return result;
};

본 해답은 힙에 요소를 넣는 행위에서 nums1과 nums2가 정렬된 상태를 활용하였습니다. 따라서, 필자의 해답과 달리 선형 시간을 사용할 수 있습니다.