MinHeap 정렬 - javascript

이해 후, 그냥 암기해라. 

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

    // 힙의 크기를 반환
    size() {
        return this.heap.length;
    }

    // 힙이 비어있는지 확인
    isEmpty() {
        return this.size() === 0;
    }

    // 부모 노드의 인덱스를 반환
    parentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    // 왼쪽 자식 노드의 인덱스를 반환
    leftChildIndex(index) {
        return 2 * index + 1;
    }

    // 오른쪽 자식 노드의 인덱스를 반환
    rightChildIndex(index) {
        return 2 * index + 2;
    }

    // 두 노드의 값을 교환
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // 요소를 추가하고, 힙 성질을 유지
    add(element) {
        this.heap.push(element);
        this.bubbleUp();
    }

    // 힙에서 최소값을 추출하고, 힙 성질을 유지
    poll() {
        if (this.isEmpty()) {
            return null;
        }
        if (this.size() === 1) {
            return this.heap.pop();
        }
        const item = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return item;
    }

    // 추가된 요소를 적절한 위치로 이동
    bubbleUp() {
        let index = this.size() - 1;
        while (index > 0 && this.heap[index] < this.heap[this.parentIndex(index)]) {
            this.swap(index, this.parentIndex(index));
            index = this.parentIndex(index);
        }
    }

    // 루트 노드를 적절한 위치로 이동
    bubbleDown() {
        let index = 0;
        while (this.leftChildIndex(index) < this.size()) {
            let smallerChildIndex = this.leftChildIndex(index);
            if (this.rightChildIndex(index) < this.size() && this.heap[this.rightChildIndex(index)] < this.heap[smallerChildIndex]) {
                smallerChildIndex = this.rightChildIndex(index);
            }

            if (this.heap[index] <= this.heap[smallerChildIndex]) {
                break;
            }

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

// 사용 예
const minHeap = new MinHeap();
minHeap.add(5);
minHeap.add(3);
minHeap.add(8);
minHeap.add(1);
console.log(minHeap.poll()); // 1
console.log(minHeap.poll()); // 3
console.log(minHeap.poll()); // 5
console.log(minHeap.poll()); // 8