이진 힙(Binary Heap) 정리

• 알고리즘 문제 풀이를 진행하다 다익스트라 알고리즘 문제를 접하게 되었다.
• 다익스트라 알고리즘이 유명한 알고리즘이기도 하고, 이번 기회에 다익스트라 알고리즘 구현에 잘 쓰이는 이진 힙 및 우선순위 큐에 대해 알아보는 것이 좋겠다 싶어 강의를 들은 내용을 간략히 기록한다.

강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다.

---

힙 (Heap)

: 트리와 비슷한 자료구조. 다만 트리와 달리 부모와 자식 노드 사이의 관계에 대한 조건이 존재한다. 이 조건은 힙의 종류에 따라 다름.

• 최대 힙(Max Heap): 부모가 늘 자식보다 큰 값을 지닌다.
• 최소 힙(Min Heap): 부모가 늘 자식보다 작은 값을 지닌다.

 

이진 힙(Binary Heap)

: 힙 중에서도 오직 2개의 자식 노드를 가질 수 있는 힙. 이진 힙은 아래와 같은 특징을 갖는다.

• 언제나 가능한 가장 적은 공간을 차지한다.
  한쪽으로 과하게 치우칠(Skewed) 수 있는 트리와 달리, 언제나 트리의 다음 레벨을 작성하기 전 왼쪽/오른쪽 자식 노드를 다 채워야 한다. (== 완전 이진트리를 형성한다!)
• 최대 두 개의 자식을 가질 수 있는 이진 트리 형태이다.

 

이진 힙의 표현

이진 힙은 배열의 형태로 표현한다고 했을 때, 부모-자식 노드는 다음과 같은 관계를 갖는다.

• 부모 노드의 인덱스가 n일 때, 자식 노드의 인덱스는 2n + 1(왼쪽 자식 노드) / 2n + 2(오른쪽 자식 노드) 이다.
• 반대로, 자식 노드의 인덱스가 n일 때, 부모 노드의 인덱스는 n / 2를 내림한 결과(Math.floor(n / 2))이다.

위는 다음과 같이 이진 힙을 배열에 넣었을 때 확인해볼 수 있다.

이진 힙을 배열로 표현한 모습

• 56을 배열에 넣었을 때의 인덱스는 1이다. 이를 위의 공식에 대입해 자식 노드의 인덱스를 구하면 3(19)과 4(31)이다.
• 반대로, 56의 자식 노드인 19의 인덱스는 3이다. 이를 위의 공식에 대입해 부모 노드의 인덱스를 구하면 1(56)이다.

 

최대 이진 힙의 구현

위의 그림처럼, 이진 힙의 요소들은 배열(혹은 리스트)에 저장할 수 있다.

insert

1. 힙 배열 끝에 추가할 요소를 push 한다. (== 트리의 가장 마지막 레벨에 새로 추가된 요소가 위치하게 된다.)
2. 위에서 추가한 요소가 올바른 자리에 위치할 때까지 계속해서 요소를 올린다. (Bubble up)
   - 올바른 자리란, 최대 이진 힙에서는 '부모가 자신보다 더 커질 때까지', 최소 이진 힙에서는 '부모가 자신보다 더 작아질 때까지'를 의미한다.

 

remove

1. 루트를 제거하는 대신, 힙 배열 가장 끝에 위치한 요소를 대신 루트 자리에 넣는다.
2. 새롭게 추가된 루트가 올바른 자리에 위치할 때까지 계속해서 요소를 내린다. (Bubble down or Sink down)
   - 올바른 자리를 찾는 것이므로, 현재 노드의 자식 중 현재 노드의 값보다 더 큰(최대 힙) 자식을 올린다.
   - 만약 두 자식이 모두 현재 노드보다 크면, 둘 중 더 큰 값을 올린다.

위의 내용을 종합해 아래와 같은 코드를 작성할 수 있다.

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    insert(node) {
        this.heap.push(node);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.heap.length - 1;
        const node = this.heap[idx];
        
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.heap[parentIdx];
            
            if(node <= parent) break; // 현재 노드가 부모보다 작게 되면 올림이 끝난다.
            
            // 현재 노드가 부모보다 클 경우, 부모와 현재 노드를 서로 바꾼다(== 현재 노드를 위로 올린다)
            this.heap[parentIdx] = node;
            this.heap[idx] = parent;
            idx = parentIdx;
        }
    }
    remove() {
    	// 루트를 빼내어 반환, 루트를 빼낸 자리엔 힙 맨 끝에 위치한 노드를 넣는다.
    	const root = this.heap[0];
        const endNode = this.heap.pop();
        
        if (this.heap.length > 0) {
        	// 옮긴 노드가 올바른 자리에 위치할 때까지 아래로 내린다.
        	this.heap[0] = end;
            this.bubbleDown();
        }
        
        return root;
    }
    bubbleDown() {
    	let idx = 0;
        let node = this.heap[0];
        const length = this.heap.length;
        
        while (true) {
        	// 노드의 좌/우측 자식 노드를 구하고, 값을 비교하여 자신보다 더 큰 자식을 위로 올린다.
        	const leftChildIdx = 2 * idx + 1;
            const rightChildIdx = 2 * idx + 2;
            let swap = null;
            
            if (leftChildIdx < length) {
            	if (this.heap[leftChildIdx] < node) {
                	swap = leftChildIdx;
                }
            }
            if (rightChildIdx < length) {
            	if (
                	(swap === null && this.heap[rightChildIdx] < node) ||
                    (swap !== null && this.heap[rightChildIdx] < this.heap[swap])
                ) {
                	swap = rightChildIdx;
                }
            }
            
            // 만약 자식을 위로 올리지 않았다면, 이미 현재 노드가 자식보다 큰 상태(== 올바른 자리에 위치)
            // 반복문을 끝낸다.
            if (swap === null) break;
            this.heap[idx] = this.heap[swap];
            this.heap[swap] = node;
            idx = swap;
        }
    }
}

 

 

이진 힙의 Big O

• insert: O(log n)
• remove: O(log n)
• search: O(n)

 

우선순위 큐(Priority Queue)

: 큐의 각 요소가 우선순위를 갖는 것을 의미한다. 따라서 우선순위가 더 높은 요소가 먼저 처리되는 성질을 지닌다.

→ 우선순위 큐의 구현에는 이진 힙이 주로 사용된다.

 

이진 힙을 이용한 우선순위 큐의 구현

• 기본적으로 위의 코드에서 변하는 것은 별로 없음.
• 그러나 우선순위 큐는 그 안의 값 + 별도의 순위가 존재하기 때문에, 현재 노드의 값이 아닌 우선순위의 크기를 비교하며 힙 연산을 수행하게 만들면 된다.

---

• 다익스트라 알고리즘에서 시작하여 많은 길을 건너 온 기분...
• 다음 글에서는 우선순위 큐를 사용한 다익스트라 알고리즘 구현을 작성할 예정이다.