[클라우딩 어플리케이션 엔지니어링 TIL] - DAY 20

힙(Heap)

최댓값(Max) 또는 최솟값(Min)을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)의 일종이다. 힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리 노드에 오게되는 특징이 있어며, 이를 이용해 우선순위 큐(Priority Queue)를 구현할 때 내부적으로 이용하는 자료구조이다.

힙의 종류

• 최대 힙(Max Heap): 모든 노드가 자식 노드보다 작거나 같은 값을 가지는 힙
• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 값을 가지는 힙

최소 힙(Min Heap) 구현

최소 힙을 구현하는데 필요한 삽입 연산

1.  힙의 마지막 노드에 새로은 노드 추가
2. 새로운 노드를 추가한 위치에서부터, 부모 노드와 새로 추가된 노드의 값을 비교
3. 만약 새로 추가한 노드의 값이 부모 노드보다 작다면, 부모 노드와 새로 추가한 노드 위치 교환
4. 이전 단계에서 교환된 노드와 부모 노드의 값을 비교하여 이 단계를 반복

class MinHeap {
    constructor() {
        this.heap = [null];
    }
    push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);

	    // 부모 노드가 존재하고 삽입할 값이 부모 노드보다 작은 경우
        while (parentIndex !== 0 && this.heap[parentIndex] > value) {
            this._swap(parentIndex, currentIndex)

            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    pop() {
        if (this.isEmpty()) return; // 힙이 빈 경우
        if (this.heap.length === 2) return this.heap.pop(); // 루트 정점만 남은 경우
        const returnValue = this.heap[1]; // 반환할 최솟값
        this.heap[1] = this.heap.pop(); // 힙의 끝에 있는 값을 루트 노드로 이동

        let currentIndex  = 1;
        let leftIndex = 2;
        let rightIndex = 3;
        
        // 루트 노드부터 자식 노드를 비교하면서 작은 값 탐색 후 교환
        while (this.heap[currentIndex] > this.heap[leftIndex] || 
               this.heap[currentIndex] > this.heap[rightIndex]) {
            if (this.heap[leftIndex] > this.heap[rightIndex]) {
                this._swap(rightIndex, currentIndex)
                currentIndex = rightIndex;
            } else {
                this._swap(leftIndex, currentIndex)
                currentIndex = leftIndex;
            }
            leftIndex = currentIndex * 2;
            rightIndex = currentIndex * 2 + 1;
        }
        return returnValue;
    }
}
_swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
isEmpty() {
    return this.heap.length === 1;
}

 

참고

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)