코딩테스트 문제를 풀다가 우선순위 큐를 사용하는 문제가 있었는데 자바스크립트는 우선순위 큐를 직접 구현해서 사용해야 하기 때문에 이참에 한번 구현과정을 작성해보고자 한다.
우선순위 큐란?
우선순위 큐는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. 우선순위 큐는 보통 힙(Heap)이라는 트리를 사용해서 구현한다. 힙은 가장 크거나 작은 원소를 찾는 데 최적화된 형태의 이진트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 크거나 작은 원소를 꺼내는 연산을 모두 O(log N)시간에 수행할 수 있다.
힙이란?
힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루트에 들어가기 때문에 최대 원소를 빠르게 찾는 것이 가능하다.
힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 다음과 같은 제약을 둔다.
-
마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
-
마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져야 한다.
즉, 트리의 위부터 아래, 왼쪽부터 오른쪽의 순서로 빠짐없이 가득차있는 완전 이진트리의 형태를 가져야 한다는 말이다.
트리의 레벨은 같은 깊이를 가지는 노드들의 집합을 의미한다. 이 규칙 덕분에 트리의 높이는 O(log N)이 된다.
자바스크립트 우선순위 큐 구현
힙이 요구하는 엄격한 모양 규칙 덕분에 우리는 트리의 노드 개수만 알면 트리 전체의 구조를 알 수 있다. 이 장점을 살려서 힙 구현은 보통 배열 하나로 전체 트리를 표현할 수 있다.
-
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 = [];
}
push(value) {
const heap = this.heap;
heap.push(value);
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(log N)이다.
최대 원소 꺼내기
최대 원소는 배열의 첫 원소다. 그럼 이 원소를 추출하고나서 루트를 다시 채워줘야 한다.
간단하게 삽입과 반대로 배열의 마지막 원소를 루트에 넣어주면 된다. 그 다음부터는 대소 관계를 만족시키면 된다. 두 자식이 가지고 있는 원소 중 더 큰 원소를 선택해 루트가 갖고 있는 원소와 바꾼다. 이 작업을 루트에서 트리의 바닥, 혹은 두 자손이 모두 자기 자신 이하의 원소를 가지고 있을 때까지 반복하면 된다.
class Heap {
constructor() {
this.heap = [];
}
push(value) {...}
pop() {
const heap = this.heap;
if (heap.length <= 1) return heap.pop();
const pop = heap[0]; // 추출한 원소
heap[0] = heap.pop(); // 마지막 원소를 루트에
let currNodeIdx = 0; // 루트 노드의 인덱스
while (1) {
let [left, right] = [currNodeIdx * 2 + 1, currNodeIdx * 2 + 2]; // 자식 노드
if (left >= heap.length) break; // 트리의 바닥(리프)에 도달
let next = currNodeIdx; // next = 이동할 위치
if (heap[next] < heap[left]) {
// 왼쪽 자식이 더 크다면
next = left;
} else if (right < heap.length && heap[next] < heap[right]) {
// 오른쪽 자식이 더 크다면
next = right;
}
if (next === currNodeIdx) break; // 부모 노드가 자식들 보다 더 크다면
// 부모노드와 자식 노드의 위치 변경
[heap[currNodeIdx], heap[next]] = [heap[next], heap[currNodeIdx]];
// 현재 노드 위치를 이동한 위치로 변경
currNodeIdx = next;
}
return pop;
}
}최종 코드
class Heap {
constructor() {
this.heap = [];
}
push(value) {
const heap = this.heap;
heap.push(value);
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);
}
}
pop() {
const heap = this.heap;
if (heap.length <= 1) return heap.pop();
const pop = heap[0];
heap[0] = heap.pop();
let currNodeIdx = 0;
while (1) {
let [left, right] = [currNodeIdx * 2 + 1, currNodeIdx * 2 + 2];
if (left >= heap.length) break;
let next = currNodeIdx;
if (heap[next] < heap[left]) {
next = left;
} else if (right < heap.length && heap[next] < heap[right]) {
next = right;
}
if (next === currNodeIdx) break;
[heap[currNodeIdx], heap[next]] = [heap[next], heap[currNodeIdx]];
currNodeIdx = next;
}
return pop;
}
}정상적으로 동작하는지 확인하기 위해 간단한 테스트 코드를 작성했다.
const heap = new Heap();
heap.push(5);
heap.push(2);
heap.push(9);
console.log(heap.pop()); // 9
console.log(heap.pop()); // 5
console.log(heap.pop()); // 2pop할 때마다 제일 큰 값이 출력되면 잘 동작한다는 뜻이다.
