[Data Structure] 비선형 - 우선순위 큐

'우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다.

우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다.

여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자.

 

힙의 정의

힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루트에 들어가기 때문에 최대 원소를 빨리 찾는 것이 가능하다.

힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 다음과 같은 제약을 둔다.

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져야 한다.

즉, 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득차있는 완전 이진트리의 형태를 가져야 한다는 말이다.

트리의 레벨은 같은 깊이를 가지는 노드들의 집합을 의미한다. 이 규칙 덕분에 트리의 높이는 O(lgN)이 된다.

 

힙의 구현

힙이 요구하는 엄격한 모양 규칙 덕분에 우리는 트리의 노드 개수만 알면 트리 전체의 구조를 알 수 있다. 이 장점을 살려서 힙 구현은 보통 배열 하나로 전체 트리를 표현한다.

• A[i]의 왼쪽 자손은 A[i*2+1]
• A[i]의 오른쪽 자손은 A[i*2+2]
• A[i]의 부모는 A[(i-1)/2]

 

삽입

새 원소를 넣기 위해서는 일단 새 원소의 위치를 알아야 한다. 하지만 우리는 이미 새 원소가 들어갈 위치를 안다. n개의 노드를 가진 배열에 새 원소는 n번째 인덱스에 새로 추가될 것이다.

배열의 끝에 새 원소를 넣어줬다면 이제 대소관계를 만족시키면 된다. 새 원소를 부모 노드와 비교하고, 부모 노드가 자식 노드보다 작으면 두 원소의 위치를 바꿔주면 된다. 새 원소가 더 크거나 같은 원소를 가진 부모를 만나거나 루트에 도달할 때까지 반복한다.

class Heap {
    constructor() {
        this.heap = [];
    }
    /**
    * @param {number} newValue
    */
    push(newValue) {
        const heap = this.heap;
        heap.push(newValue);
        let index = heap.length - 1, parent = Math.floor((index - 1) / 2);
        while(index > 0 && heap[parent] < heap[index]) {
            [heap[parent], heap[index]] = [heap[index], heap[parent]];
            index = parent;
            parent = Math.floor((index - 1) / 2);
        }
    }
}

while문이 한 번 돌아갈 때마다 트리의 한 레벨을 올라가기 때문에 시간복잡도는 트리의 높이인 O(lgN)이다.

 

최대 원소 꺼내기

최대 원소는 배열의 첫 원소다. 그럼 이 원소를 빼고나서 뭐가 루트에 와야할까?

간단하다. 삽입과 반대로 배열의 마지막 원소를 루트에 넣어주면 된다. 그 다음부터는 대소관계를 만족시키면 된다. 두 자식이 가지고 있는 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 원소와 바꾼다. 이 작업을 루트에서 트리의 바닥, 혹은 두 자손이 모두 자기 자신 이하의 원소를 갖고 있을 때까지 반복하면 된다.

class Heap {
    constructor() {
        this.heap = [];
    }
    /**
    * @param {number} newValue
    */
    push(newValue) {
        const heap = this.heap;
        heap.push(newValue);
        let index = heap.length - 1, parent = Math.floor((index - 1) / 2);
        while(index > 0 && heap[parent] < heap[index]) {
            [heap[parent], heap[index]] = [heap[index], heap[parent]];
            index = parent;
            parent = Math.floor((index - 1) / 2);
        }
    }
    /**
    * @return {number}
    */
    pop() {
        const heap = this.heap;
        if(heap.length <= 1) return heap.pop();
        const ret = heap[0];
        heap[0] = heap.pop();
        let here = 0;
        while(1) {
            let left = here * 2 + 1, right = here * 2 + 2;
            // 리프에 도달
            if(left >= heap.length) break;
            // heap[here]가 내려갈 위치를 찾는다.
            let next = here;
            if (heap[next] < heap[left]) next = left;
            if (right < heap.length && heap[next] < heap[right]) next = right;
            if (next === here) break;
            [heap[here], heap[next]] = [heap[next], heap[here]];
            here = next;
        }
        return ret;
    }
}