정제 완료...!

function makeMaxHeap() {
    const heap = []

    function isValidParent(i, j) {
        return heap[i] >= heap[j]
    }

    function swap(i, j) {
        ;[heap[i], heap[j]] = [heap[j], heap[i]]
    }

    function parent(i) {
        return Math.floor((i - 1) / 2)
    }

    function child(i) {
        const [l, r] = [2 * i + 1, 2 * i + 2]
        if (heap[l] === undefined) {
            return undefined
        }
        if (heap[r] === undefined) {
            return l
        }
        return isValidParent(l, r) ? l : r
    }

    function push(x) {
        heap.push(x)
        const i0 = heap.length - 1
        for (let [i, p] = [i0, parent(i0)]; p >= 0; [i, p] = [p, parent(p)]) {
            if (isValidParent(p, i)) {
                break
            }
            swap(i, p)
        }
    }

    function pop() {
        if (heap.length <= 1) {
            return heap.pop()
        }

        swap(0, heap.length - 1)
        const result = heap.pop() // should pop here

        const i0 = 0
        for (let [i, c] = [i0, child(i0)]; c !== undefined; [i, c] = [c, child(c)]) {
            if (isValidParent(i, c)) {
                break
            }
            swap(i, c)
        }
        return result
    }

    return { push, pop }
}

• 주의사항

  • swap 이후에는 child 함수의 결과가 바뀌기 때문에 child 변수를 미리 저장해놓고 사용해야 한다.

  • child 함수 계산 시 heap[i] === undefined 대신 heap 길이로 계산할 경우 off-by-one error 조심