자바스크립트로 우선순위 큐(PriorityQueue)에 요소 추가하는 방법

우선순위 큐(PriorityQueue)에 요소를 추가(enqueue)한다는 것은 각 요소의 우선순위 순서에 맞게 배열에 삽입하는 것을 의미합니다. 이 글에서는 숫자가 클수록 더 높은 우선순위를 가진다고 가정하겠습니다.

동작 방식은 다음과 같습니다. 컨테이너(배열)를 처음부터 끝까지 순회하면서 새로 추가할 요소보다 낮은 우선순위를 가진 요소를 발견하면, 그 위치 바로 앞에 새 요소를 삽입합니다. 만약 끝까지 순회해도 적절한 위치를 찾지 못했다면, 해당 요소는 가장 높은 우선순위를 가지므로 컨테이너의 맨 끝에 추가하면 됩니다.

이때 주의할 점은 단순히 값만 저장하는 것이 아니라, 데이터(data)와 우선순위(priority)를 함께 담은 요소 객체를 생성한다는 것입니다. 이를 바탕으로 enqueue 함수는 다음과 같이 구현할 수 있습니다.

구현 예제

enqueue(data, priority) {
    // 큐가 가득 찼는지 확인
    if (this.isFull()) {
        console.log("Queue Overflow!");
        return;
    }
    let currElem = new this.Element(data, priority);
    let addedFlag = false;
    // 우선순위에 맞는 위치를 찾아 삽입
    for(let i = 0; i < this.container.length; i ++) {
        if(currElem.priority < this.container[i].priority) {
            this.container.splice(i, 0, currElem);
            addedFlag = true; break;
        }
    }
    // 적절한 위치를 찾지 못한 경우 맨 뒤에 추가
    if (!addedFlag) {
        this.container.push(currElem);
    }
}

동작 확인하기

이 함수가 올바르게 동작하는지 직접 테스트해 볼 수 있습니다.

let q = new PriorityQueue(4);
q.enqueue("Hello", 3);
q.enqueue("World", 2);
q.enqueue("Foo", 8);
q.display();

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

[ { data: 'World', priority: 2 },
  { data: 'Hello', priority: 3 },
  { data: 'Foo', priority: 8 } ]

출력 결과를 보면 요소들이 우선순위에 따라 오름차순으로 정렬되어 있는 것을 확인할 수 있습니다. 즉, 우선순위가 가장 낮은 요소가 배열의 맨 앞에 위치하게 됩니다.

동작 원리 정리

이 enqueue 함수의 동작 방식은 삽입 정렬(Insertion Sort)에서 새로운 값을 제자리에 삽입하는 과정과 매우 유사합니다. 새 요소를 추가할 때마다 기존 요소들과 우선순위를 비교하며 알맞은 자리를 찾아 넣기 때문에, 큐 전체가 항상 정렬된 상태를 유지하게 됩니다.

다만 이 방식은 최악의 경우 모든 요소를 비교해야 하므로 시간 복잡도가 O(n)입니다. 요소 개수가 많다면 힙(Heap) 기반의 우선순위 큐(O(log n))를 고려하는 것이 좋습니다. 하지만 소규모 데이터나 학습 목적으로는 위와 같은 배열 기반 구현이 직관적이고 이해하기 쉬운 장점이 있습니다.