알고리즘 / 최대 힙 / JS 구현
정제 완료...!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 조심
