자료구조 - 우선순위 큐(Priority Queue)

우선순위 큐

우선순위 큐는 ADT로 언제든지 가장 우선순위가 높은 요소에 접근이 가능한 큐를 의미한다.

 

우선순위 큐는 기본적으로 큐이기 때문에 데이터를 삽입하고 삭제할 수 있는 Enqueue와 Dequeue가 존재한다.

 

이때 Enqueue는 기존의 queue와 동일하게 그냥 삽입하면되지만 Dequeue의 경우 가장 먼저 입력된 값이 아닌 우선순위가 높은 예를들면 가장 큰 값이 출력되야 한다.

 

우선순위 큐는 우선순위가 높은 값을 가장 가져올 수만 있으면 되기 때문에 Unsorted List, Sorted List , Linked List, Binary Search Tree, Heap 등 어떠한 과정으로도 만들 수 있다.

 

하지만 Unsorted List는 Dequeue를 하는 과정에서 모든 요소들을 확인해야하기 때문에 매우 비효율적이고 Sorted List와 Linked List는 Enqueue를 하는 과정이 매우 비효율 적이여서 사용하기 부적절하다.

 

Binary Search Tree의 경우 Enqueue와 Dequeue모두 평균적으로 $O(\log_2 N)$이 걸리지만 최악의 경우는 List와 동일한 복잡도가 생길 수 있는 문제가 있다.

 

따라서 Heap을 통해 우선순위 큐를 구현하면 Complete Binary Tree이기 떄문에 어떠한 경우에도 시간 복잡도가 $O(\log_2 N)$만큼 소모되어 가장 적절하다고 볼 수 있다.

 

Dequeue & Enqueue

heap에서 우선순위가 root에 있다고 하면 Dequeue는 root의 값을 제거하고 heap에서 Delete를 하는 과정을 동일하게 수행하면 된다.

 

Enqueue의 경우도 heap에서 새로운 값을 insert해주는 과정과 동일함으로 똑같이 실행하면 된다.

void Dequeue(ItemType& item) {
    if (length == 0)
        throw EmptyPQ();
    else {
        item = items.elements[0]; //가장 큰 값
        items.elements[0] = items.elements[length - 1];
        length--;
        items.ReheapDown(0, length - 1);
    }
}

void Enqueue(ItemType newItem) {
    if (length == maxItems)
        throw FullPQ();
    else {
        length++;
        items.elements[length - 1] = newItem;
        items.ReheapUp(0, length - 1);
    }
}