우선순위 큐

우선순위 큐(Priority Queue)는 큐와 비슷한 자료구조로, 각각의 요소에 우선순위가 할당되어 있고, 우선순위가 높은 요소가 먼저 처리되는 특징을 가지고 있습니다.

우선순위 큐는 보통 이진힙(Binary Heap) 자료구조를 이용하여 구현됩니다. 이진힙은 완전 이진트리의 일종으로, 부모 노드가 자식 노드보다 항상 큰 값을 가지는 최대 힙(Max Heap)과 부모 노드가 자식 노드보다 항상 작은 값을 가지는 최소 힙(Min Heap)으로 구분됩니다.

 

 가장 우선순위가 높은 요소는 큐의 맨 앞쪽에 위치하게 되고, 그 다음으로 우선순위가 높은 요소는 그 다음 위치에 위치하게 됩니다.

 우선순위 큐에서 요소를 삭제하면, 가장 우선순위가 높은 요소가 삭제되게 됩니다. 이러한 특성 때문에 우선순위 큐는 주로 최솟값 또는 최댓값을 찾아야 하는 경우에 사용됩니다.

C++에서는 priority_queue라는 라이브러리를 제공하여 우선순위 큐를 쉽게 구현할 수 있습니다. priority_queue는 표준 라이브러리인 <queue> 헤더 파일에 정의되어 있습니다.

아래는 priority_queue를 이용한 우선순위 큐 예시입니다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq; // 우선순위 큐 선언

    // 값 삽입
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);

    // 큐의 크기 출력
    cout << "size: " << pq.size() << '\n';

    // 큐의 모든 요소 출력
    while (!pq.empty()) {
        cout << pq.top() << ' '; // 우선순위가 가장 높은 요소 출력
        pq.pop(); // 우선순위가 가장 높은 요소 제거
    }
    cout << '\n';

    return 0;
}

 

우선순위 큐를 이용한 오름차순 정렬 예시입니다.

#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);

    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

 위의 코드에서는 priority_queue를 선언할 때, 세 개의 인자를 전달합니다. 첫 번째 인자는 우선순위 큐에 저장될 데이터 타입을, 두 번째 인자는 내부 컨테이너 타입을, 세 번째 인자는 비교 함수를 나타냅니다. 이때, 비교 함수를 greater<int>로 지정하면 오름차순으로 정렬된 큐를 구현할 수 있습니다. 큐에 데이터를 삽입한 후, top() 함수를 이용하여 큐의 가장 작은 값을 출력하고 pop() 함수를 이용하여 큐에서 제거합니다.