[C++] priority_queue (우선순위 큐)

std::priority_queue는 C++ 표준 라이브러리에서 제공하는 컨테이너 어댑터로, 우선순위 큐를 구현합니다. 우선순위 큐는 일반적인 큐와 달리, 요소들이 우선순위에 따라 정렬되어 큐의 앞부분에 위치하며, 가장 높은 우선순위를 가진 요소가 먼저 꺼내집니다.

 

주요 특징:

• 우선순위: std::priority_queue는 기본적으로 **최대 힙(Max-Heap)**으로 구현되어 있어, 가장 큰 요소가 항상 맨 앞에 위치합니다. 이는 자동으로 내림차순으로 정렬된다는 의미입니다.
• 기본 동작: std::priority_queue는 std::vector 또는 std::deque와 같은 기본 컨테이너를 내부적으로 사용하여 데이터를 저장하며, 힙을 사용하여 요소를 정렬합니다.

 

 

사용법:

1. 기본 사용법 (최대 힙)

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);

    std::cout << "Top element: " << pq.top() << std::endl;  // 20

    pq.pop();  // 20 제거

    std::cout << "Top element after pop: " << pq.top() << std::endl;  // 10

    return 0;
}

• push: 요소를 우선순위 큐에 추가합니다. (추가하고 자동으로 정렬 됨.)
• top: 큐의 가장 앞에 있는 요소(우선순위가 가장 높은 요소)를 반환합니다.
• pop: 큐의 가장 앞에 있는 요소를 제거합니다.
• empty: 큐가 비어 있는지 확인합니다.
• size: 큐의 요소 개수를 반환합니다.

 

2. 최소 힙으로 사용하기 (std::greater 사용)

기본적으로 std::priority_queue는 최대 힙을 구현합니다. 최소 힙을 구현하려면 std::greater를 사용하여 비교 기준을 변경해야 합니다. 

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

 

std::priority_queue의 템플릿 인자 중 두 번째 인자인 Container는 기본값으로 std::vector<T>가 사용됩니다. 따라서, 별도로 명시하지 않으면 priority_queue는 내부적으로 std::vector를 사용하여 요소들을 저장하고 관리합니다.

세 번째 인자인 Compare는 기본값으로 std::less<T>가 사용됩니다. 이 std::less가 우선순위 큐를 최대 힙으로 동작하게 만듭니다.

기본 인자 설정

• Container: std::vector<T> (생략 가능)
• Compare: std::less<T> (생략 가능)

최소 힙을 만들기 위해 필요한 것

• std::greater<T>를 사용: 최소 힙을 만들려면 세 번째 인자에 std::greater<T>를 명시적으로 지정해야 합니다.

 

3. 사용자 정의 구조체를 사용한 우선순위 큐

복잡한 데이터를 우선순위 큐에 저장할 때는 사용자 정의 비교 함수를 사용해야 합니다.

#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int priority;
    std::string name;

    bool operator<(const Task& other) const {
        return priority < other.priority;  // 큰 값이 우선
    }
};

int main() {
    std::priority_queue<Task> tasks;

    tasks.push({3, "Task 1"});
    tasks.push({1, "Task 2"});
    tasks.push({2, "Task 3"});

    while (!tasks.empty()) {
        std::cout << tasks.top().name << " with priority " << tasks.top().priority << std::endl;
        tasks.pop();
    }

    return 0;
}

 

 

핵심 개념 요약:

• 힙 기반: std::priority_queue는 힙을 사용하여 우선순위를 유지합니다. 기본적으로 최대 힙이지만, 비교 함수를 제공하여 최소 힙 또는 사용자 정의 우선순위를 구현할 수 있습니다.
• 시간 복잡도: push, pop 연산의 시간 복잡도는 O(log n)이며, top 연산은 O(1)입니다. 이는 힙의 높이에 비례하여 효율적으로 동작합니다.
• 응용: 우선순위 큐는 다양한 알고리즘에서 사용되며, 특히 다익스트라의 최단 경로 알고리즘, 프림의 최소 신장 트리 알고리즘, 힙 정렬 등에 사용됩니다.

 

 

결론:

std::priority_queue는 특정 기준에 따라 요소들이 자동으로 정렬되고, 가장 높은 우선순위 요소가 먼저 처리되는 자료 구조입니다. 기본적으로 최대 힙을 제공하며, 필요에 따라 최소 힙이나 사용자 정의 우선순위를 사용할 수 있습니다. 이를 통해 다양한 알고리즘 및 데이터 처리 문제를 효율적으로 해결할 수 있습니다.