[LeetCode] 373. Find K Pairs with Smallest Sums

😎풀이

1. 최소 힙 클래스 선언
2. nums1[i]의 요소와 nums2[0]의 요소 쌍을 미리 입력
   2-1. WHY?, nums1[i]가 pop 되는 시점에 nums2[j]요소와의 쌍을 입력해 최소 힙 목록 맞춤
3. 가장 작은 합계를 갖는 쌍을 순서대로 추출하고, 다음 검사 대상 요소를 push함

type NodeType = {
    sum: number
    i: number
    j: number
}
class CustomMinHeap {
    private heap: NodeType[]
    constructor() {
        this.heap = []
    }
    push(node: NodeType) {
        this.heap.push(node)
        this.heapifyUp()
        return this.heap
    }
    heapifyUp() {
        let idx = this.size() - 1
        while(idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2)
            if(this.heap[idx].sum >= this.heap[parentIdx].sum) break
            [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]]
            idx = parentIdx
        }
        return
    }
    pop() {
        if(this.size() < 1) return null
        if(this.size() === 1) return this.heap.pop()
        const poped = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.heapifyDown()
        return poped
    }
    heapifyDown() {
        const heapLen = this.size()
        let idx = 0
        while(idx < heapLen) {
            const leftChildIdx = idx * 2 + 1
            const rightChildIdx = idx * 2 + 2
            let smallestIdx = idx
            if(leftChildIdx < heapLen && this.heap[leftChildIdx].sum < this.heap[smallestIdx].sum) smallestIdx = leftChildIdx
            if(rightChildIdx < heapLen && this.heap[rightChildIdx].sum < this.heap[smallestIdx].sum) smallestIdx = rightChildIdx
            if(idx === smallestIdx) break
            [this.heap[idx], this.heap[smallestIdx]] = [this.heap[smallestIdx], this.heap[idx]]
            idx = smallestIdx
        }
        return
    }
    size() {
        return this.heap.length
    }
}

function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
    const minHeap = new CustomMinHeap()
    const minLoop = Math.min(nums1.length, k)
    for(let i = 0; i < minLoop; i++) {
        const sum = nums1[i] + nums2[0]
        minHeap.push({ sum, i, j: 0 })
    }
    const result = []
    while(result.length < k && minHeap.size()) {
        const { sum, i, j } = minHeap.pop()
        result.push([nums1[i], nums2[j]])
        if(nums2.length > j + 1) {
            minHeap.push({
                sum: nums1[i] + nums2[j + 1],
                i,
                j: j + 1
            })
        }
    }
    return result
};