우선순위 큐 (Priority Queue)

우선순위 큐 (Priority Queue) 설명:

우선순위 큐는 항목들이 우선순위에 따라 저장되는 자료구조입니다. 기본 큐와는 달리 우선순위 큐에서는 가장 높은 (또는 가장 낮은) 우선순위를 가진 항목이 먼저 꺼내집니다. 우선순위 큐는 이진 힙, 피보나치 힙 등 여러 방법으로 구현될 수 있으며, 그 중 이진 힙은 가장 일반적인 구현 방법입니다.

기본 연산:
1. insert(item, priority): 우선순위와 함께 항목을 큐에 추가한다.
2. deleteMax() 또는 deleteMin(): 가장 높은 (또는 낮은) 우선순위를 가진 항목을 꺼낸다.
3. peek(): 가장 높은 (또는 낮은) 우선순위의 항목을 조회한다. (제거하지 않음)
4. isEmpty(): 우선순위 큐가 비어있는지 확인한다.

JavaScript에서의 우선순위 큐 구현 예제:

간단한 이진 힙 기반의 우선순위 큐 구현은 복잡할 수 있으므로, 여기서는 기본적인 방식을 사용하여 구현해보겠습니다.

class PriorityQueue {
    constructor() {
        this.items = [];
    }

    enqueue(item, priority) {
        const queueElement = {item, priority};
        let added = false;

        for (let i = 0; i < this.items.length; i++) {
            if (queueElement.priority < this.items[i].priority) {
                this.items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }

        if (!added) {
            this.items.push(queueElement);
        }
    }

    dequeue() {
        return this.items.shift();
    }

    front() {
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

const pq = new PriorityQueue();
pq.enqueue('Task1', 2);
pq.enqueue('Task2', 1);
pq.enqueue('Task3', 3);
console.log(pq.dequeue().item);  // Task2 (가장 높은 우선순위)

우선순위 큐의 사용 사례:
1. 알고리즘: 다익스트라의 최단 경로 알고리즘, 프림의 MST 알고리즘 등에서 사용됩니다.
2. 작업 스케줄링: 우선순위에 따른 태스크 처리.
3. 데이터 압축: 허프만 코딩 알고리즘에서 사용됩니다.

장점:
1. 특정 우선순위의 항목에 빠르게 접근할 수 있다.
2. 우선순위에 따라 항목을 처리하고 싶을 때 유용하다.

단점:
1. 간단한 구현 방법의 경우 삽입 연산의 시간 복잡도가 O(n)일 수 있다.
2. 더 복잡한 자료구조를 사용하여 O(log n)의 시간 복잡도로 삽입과 삭제를 처리할 수 있지만, 구현이 복잡해질 수 있다.

우선순위 큐는 여러 애플리케이션에서 중요한 자료구조로 활용되며, 특히 알고리즘 문제 해결에서 그 중요성이 큽니다.