우선순위 큐
이번에 네이버 부스트 캠프 베이직 과정을 진행하면서 자바스크립트를 쓰게 되었는데, 평소에는 파이썬을 자주 사용했었기 때문에 자바스크립트로 파이썬을 대체해보려고 노력했다.
다만 파이썬에는 여러가지 자료구조와 함수들이 잘 구현되어 있는데 자바스크립트를 써보니까 우선순위 큐가 내장 라이브러리에 없었다!
이번 기회에 자바스크립트 공부 겸 힙과 우선순위 큐에 대해 다시 복습하고 직접 구현해보려고 한다.
Heap
우선 순위 큐는 힙 자료구조를 사용하기 때문에 힙이 무엇인지 알고 있어야 한다.
힙(Heap) 는 최댓값 혹은 최솟값을 빠르게 찾아내는 연산을 위해 설계된 완전 이진 트리 자료구조이다.
최댓값을 빠르게 찾고 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 최대 힙, 최솟값을 빠르게 찾고 부모노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 최소 힙이라고 부른다.
우선 순위 큐에서도 작을 수록 우선순위가 높은지, 클 수록 우선순위가 높은지에 따라 최대 힙, 최소 힙을 적절히 사용해야 한다.
보통 최소 힙 라이브러리가 내장되어 있기 때문에, 만약 클 수록 우선순위가 높다면 데이터 전체에 -1 을 곱하는 등의 처리를 통해 최소 힙을 최대 힙처럼 사용할 수도 있다.
우선 순위 큐
그렇다면 우선 순위 큐는 어떤 식으로 구현되어 있을까?
최소 힙과 최대 힙은 거의 유사하기도 하고, 위에서 말한 것처럼 활용할 수도 있기 때문에 최소 힙 우선순위 큐를 한 번 살펴보려고 한다.
javascript
class PriorityQueue {
constructor() {
this.heap = []; // 데이터를 담을 배열
}
enqueue(value) {
// 1. 힙 자료구조에 value 를 넣고
// 2. value 가 알맞은 자리를 찾아갈 수 있도록 한다. -> 아래의 bubbleUp 함수를 사용할 예정
}
dequeue() {
// 1. 힙 자료구조의 루트 노드에 해당하는 값을 임시로 저장해두고
// (pop 이 아님! pop(0)은 O(n) 의 시간복잡도를 가지기 떄문에 힙 자료구조를 사용하는 의미가 없어짐
// 2. 맨 마지막 리프 노드에 해당하는 값을 루트 노드에 저장하고,
// 3. 해당 루트 노드의 값이 알맞은 자리를 찾아갈 수 있도록 한다. -> 아래의 bubbleDown 함수를 사용할 예정
}
peek() {
// 루트 노드를 pop 하는 것이 목적이 아닌, 그저 루트 노드를 참조하고자 할 때
return this.heap.length > 0 ? this.heap[0] : null;
}
bubbleUp(index) {
// index 번 째에 해당하는 노드의 값보다 작은 값이 있다면, index 노드를 위로 올려보내야 한다.
}
bubbleDown(index) {
// index 번 째에 해당하는 노드의 값보다 큰 값이 있다면, index 노드를 아래로 내려보내야 한다.
}
swap(i, j) {
// i, j 값 스왑
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
}
함수를 구현하기 전에 간략한 설명과 함께 하나씩 구현해보자.
bubbleUp
javascript
bubbleUp(index) {
// index 번 째에 해당하는 노드의 값보다 작은 값이 있다면, index 노드를 위로 올려보내야 한다.
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2); // index 노드의 부모 노드 구하기.
if (this.heap[parentIndex] <= this.heap[index]) break; // 최소 힙이므로 부모노드는 항상 자식 노드보다 작거나 같다!
this.swap(index, parentIndex); // index 랑 부모노드랑 스왑
index = parentIndex; // 부모노드로 올라간 index 부터 반복
}
}
자식노드(index) 와 부모노드를 비교하는 bubbleUp 함수.
bubbleUp 함수는 우리가 버블정렬을 하는 것 처럼, 두 값을 비교해서 위치를 바꾸는 함수이다. 최소 힙을 구현하려고 하므로 부모노드는 항상 자식 노드보다 작거나 같아야 한다.
부모노드의 값을 구하는 방법은 Math.floor((index - 1) / 2) 인데
부모노드(0) -> 자식 노드(1, 2)
부모노드(1) -> 자식 노드(3, 4)
부모노드(n) -> 자식 노드(2n + 1, 2n + 2) 임을 알 수 있다.
따라서 자식 노드가 +1, +2(왼쪽, 오른쪽) 중에 어떤 쪽인지에 상관없이 부모노드를 구하는 방법이 위의 방법인 것이다.
bubbleDown
javascript
bubbleDown(index) {
// index 번 째에 해당하는 노드의 값보다 큰 값이 있다면, index 노드를 아래로 내려보내야 한다.
while (true) {
const leftChildIndex = 2 * index + 1; // 왼쪽 자식 노드
const rightChildIndex = 2 * index + 2; // 오른쪽 자식 노드
let smallestIndex = index; // 부모노드, 왼쪽 자식노드, 오른쪽 자식 노드 중에 가장 작은 값을 저장할 변수
if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[smallestIndex]) {
// 만약 부모노드보다 왼쪽 자식 노드가 작다면 smallestIndex 를 왼쪽 자식 노드로 변경
smallestIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallestIndex]) {
// 만약 위의 if 문에서 왼쪽 자식 노드가 작았다면 smallestIndex 는 왼쪽 자식 노드,
// 아니라면 부모 노드
// 똑같이 오른쪽 자식 노드랑 비교
smallestIndex = rightChildIndex;
}
// 만약 가장 작은 노드가 부모 노드라면 최소 힙의 조건을 만족하므로 break
if (smallestIndex === index) break;
// 자식 노드 중에 더 작은 노드(smallestIndex) 와 부모노드를 스왑
this.swap(index, smallestIndex);
//더 작은 노드의 위치에 index 노드를 두고 반복
index = smallestIndex;
}
}
bubbleDown 도 bubbleUp 와는 반대로 내려오는 것이기 때문에,
index에 해당하는 노드가 제자리를 찾을 때까지 자식 노드와의 비교를 반복한다.
enqueue, dequeue
javascript
enqueue(value) {
// 1. 힙 자료구조에 value 를 넣고
this.heap.push(value);
// 2. value 가 알맞은 자리를 찾아갈 수 있도록 한다. -> 아래의 bubbleUp 함수를 사용할 예정
this.bubbleUp(this.heap.length - 1);
}
dequeue() {
if (this.heap.length === 0) return null;
// 1. 힙 자료구조의 루트 노드(0번째 Index)에 해당하는 값을 임시로 저장해두고
// (pop 이 아님! pop(0)은 O(n) 의 시간복잡도를 가지기 떄문에 힙 자료구조를 사용하는 의미가 없어짐
const min = this.heap[0];
// 2. 맨 마지막 리프 노드에 해당하는 값을 루트 노드에 저장하고,
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
// 3. 해당 루트 노드의 값이 알맞은 자리를 찾아갈 수 있도록 한다. -> bubbleDown
this.bubbleDown(0);
}
return min;
}
추가
Comparator
javascript
constructor(comparator) {
if(comparator) this.comparator = comparator;
else this.comparator = (a, b) => a - b;
}
우선순위 큐에 어떤 타입의 비교 연산을 해야할지 모르기 때문에, comparator 도 받을 수 있도록 하면 더 좋다.
이렇게 Comparator 를 추가 했을 때, bubbleUp 과 bubbleDown 의 비교 로직을 comparator 로 하면 된다.
자바스크립트 코드
javascript
class PriorityQueue {
heap = [];
constructor(comparator) {
if(comparator) this.comparator = comparator;
else this.comparator = (a, b) => a - b;
}
enqueue(value){
const index = this.heap.push(value) - 1;
this.bubbleUp(index);
}
dequeue(){
if(this.heap.length === 0) return undefined;
const smallest = this.heap[0];
const last = this.heap.pop();
if(this.heap.length > 0){
this.heap[0] = last;
this.bubbleDown(0);
}
return smallest;
}
peek(){
return this.heap[0];
}
get length(){
return this.heap.length;
}
bubbleUp(_index){
let index = _index;
while(index > 0){
const parentIdx = Math.floor((index - 1) / 2);
if(this.comparator(this.heap[parentIdx], this.heap[index]) <= 0) break;
this.swap(index, parentIdx);
index = parentIdx;
}
}
bubbleDown(_index){
let index = _index;
while(index < this.heap.length){
let smallestIndex = index;
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
if(leftChildIndex < this.heap.length && this.comparator(this.heap[smallestIndex], this.heap[leftChildIndex]) > 0) {
smallestIndex = leftChildIndex;
}
if(rightChildIndex < this.heap.length && this.comparator(this.heap[smallestIndex], this.heap[rightChildIndex]) > 0) {
smallestIndex = rightChildIndex;
}
if(smallestIndex === index) break;
this.swap(index, smallestIndex);
index = smallestIndex;
}
}
// 위에서 봤던 swap 코드중에서 임시 배열을 만드는 것을 하고싶지 않을 때는 아래와 같이 작성하면 된다.
swap(i, j){
const store = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = store;
}
}
Subscribe to hoeeeeeh
Get the latest posts delivered right to your inbox
