우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

우선순위 큐는 각 요소가 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리되는 자료구조다.

다른 자료구조를 사용해도 되지만 이진 힙을 사용하는 것이 효율적이기 때문에 이진 힙으로 우선순위 큐를 구현하는 경우가 일반적이다.

 

아래 링크는 이진 힙 관련 포스팅:

https://catnails.tistory.com/537

 

 

필수 구현 메서드:

• enqueue(value, priority) - 우선순위와 함께 새로운 요소 추가
• dequeue() - 가장 높은 우선순위의 요소를 제거하고 반환
• peek() - 가장 높은 우선순위의 요소를 반환
• isEmpty() - 큐가 비어있는지 확인

 

시간 복잡도:

• 삽입(enqueue): O(log n)
• 삭제(dequeue): O(log n)
• 조회(peek): O(1)

활용 사례:

1. 프로세스 스케줄링
2. 네트워크 패킷 우선순위 처리
3. 이벤트 처리 시스템
4. 게임 AI의 행동 결정

우선순위 큐는 요소들의 처리 순서가 우선순위에 따라 결정되어야 하는 경우에 사용된다. 예를 들어 게임에서 AI의 행동 결정이나 운영체제의 작업 스케줄링 등에 활용된다.

 

 

구현

class PriorityQueue {
    constructor(){
        this.values = [];
    }
    enqueue(val, priority){
        let newNode = new Node(val, priority);
        this.values.push(newNode);
        this.bubbleUp();
    }
    bubbleUp(){
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.values[parentIdx];
            if(element.priority >= parent.priority) break;
            this.values[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }
    dequeue(){
        const min = this.values[0];
        const end = this.values.pop();
        if(this.values.length > 0){
            this.values[0] = end;
            this.sinkDown();
        }
        return min;
    }
    sinkDown(){
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild,rightChild;
            let swap = null;

            if(leftChildIdx < length){
                leftChild = this.values[leftChildIdx];
                if(leftChild.priority < element.priority) {
                    swap = leftChildIdx;
                }
            }
            if(rightChildIdx < length){
                rightChild = this.values[rightChildIdx];
                if(
                    (swap === null && rightChild.priority < element.priority) || 
                    (swap !== null && rightChild.priority < leftChild.priority)
                ) {
                   swap = rightChildIdx;
                }
            }
            if(swap === null) break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}

class Node {
    constructor(val, priority){
        this.val = val;
        this.priority = priority;
    }
}

let ER = new PriorityQueue();
ER.enqueue("common cold",5)
ER.enqueue("gunshot wound", 1)
ER.enqueue("high fever",4)
ER.enqueue("broken arm",2)
ER.enqueue("glass in foot",3)

 

 

다익스트라 알고리즘에서도 우선순위 큐를 사용한다.

 

https://catnails.tistory.com/541

다익스트라(Dijkstra) 알고리즘