[C++] 우선순위 큐(Priority Queue)

 

 

우선순위 큐(Priority Queue)

먼저 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 선입선출(FIFO) 형식의 자료구조입니다.

우선순위 큐(Priority Queue)는 이와 다르게 항상 우선순위가 가장 높은 데이터에만 관심이 있고, 이 데이터만 먼저 나갈 수 있는 형태의 자료구조입니다. 

 

이는 배열, 연결 리스트를 통해서도 구현이 가능하지만, 힙을 이용해야지만이 삽입, 삭제 시간을 O(logN)으로 맞출 수가 있기 때문에 보통 힙을 이용하여 우선순위 큐를 구현하고는 합니다.

 

숫자가 주어질 때마다 앞에 있는 숫자들을 전부 탐색해 그 중 최댓값을 골라야 할때 사용하면 됩니다.

 

 

 

C++에서는 이를 표현하기 위해 priority_queue라는 STL을 이용할 수 있습니다. 

 

queue STL에 포함되어 있기 때문에, 큐를  include 하여 아래와 같이 사용합니다. C++에서의 priority_queue는 기본적으로 최댓값을 우선적으로 뽑아주는 최대 우선순위 큐를 뜻합니다.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    return 0;
}

 

 

 

 

아래는 자주 사용하는 우선순위 큐의 함수입니다.

 

1. push(E)

우선순위 큐에 데이터 E를 추가합니다.

 

2. size()

현재 우선순위 큐에 들어있는 데이터의 수를 반환합니다.

 

3. empty()

현재 우선순위 큐가 비어있다면 true, 아니라면 false를 반환합니다.

 

4. top()

우선순위 큐에서 최댓값에 해당하는 데이터를 반환합니다.

 

5. pop()

우선순위 큐에서 최댓값에 해당하는 데이터를 뺍니다.

추가적으로 C++에서의 priority_queue는 pop() 호출시 삭제만 할 뿐, 해당 값을 반환하지 않습니다. 이는 C++의 철학상, 하나의 함수는 하나의 역할만 해야한다는 점과 안전성 측면에서 이렇게 설계되어져 있습니다. 꼭 유의하시기를 바랍니다.

 

 

 

사용예시

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;       // 정수를 관리할 priority_queue를 선언합니다. => 빈 우선순위 큐
    pq.push(2); 
    pq.push(9);
    pq.push(5);
    
    cout << pq.top() << endl;     // 최댓값을 출력합니다. => 9
    pq.pop();                     // 최댓값을 제거합니다.
    cout << s.size() << endl;     // 원소의 개수를 출력합니다 => 2
    while(!pq.empty()){           // 가장 큰 값부터 순서대로 출력합니다.
        cout << pq.top() << endl; // 순서대로 5 2 출력됩니다.
        pq.pop();                 // 가장 위에 있는 원소를 뺍니다.
    }

    return 0;
}

 

 

 

 

 

아래 코드는 ChatGPT가 작성한 C++ 우선순위 큐 구현 코드입니다. 힙으로 우선순위 큐를 구현한 것을 볼 수 있습니다. 참고용으로 첨부하였습니다. 

#include <vector>
#include <stdexcept>
#include <iostream>

class PriorityQueue {
private:
    std::vector<int> heap;

    void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        while (index > 0 && heap[index] > heap[parent]) {
            std::swap(heap[index], heap[parent]);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    void heapifyDown(int index) {
        int size = heap.size();
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild < size && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }

        if (rightChild < size && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }

public:
    bool isEmpty() const {
        return heap.empty();
    }

    int size() const {
        return heap.size();
    }

    void push(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int top() const {
        if (isEmpty()) {
            throw std::out_of_range("Priority queue is empty.");
        }
        return heap[0];
    }

    void pop() {
        if (isEmpty()) {
            throw std::out_of_range("Priority queue is empty.");
        }
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }
};

int main() {
    PriorityQueue pq;

    // Add elements to the priority queue
    pq.push(5);
    pq.push(2);
    pq.push(10);

    // Print the elements in descending order of priority
    while (!pq.isEmpty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

• heapifyUp 함수: 이 함수는 요소를 트리 위로 이동하여 힙 속성을 복원하는 역할을 합니다. 요소를 부모와 비교하고 필요한 경우 힙 속성이 충족될 때까지 교체합니다.
• heapifyDown 함수: 이 함수는 요소를 트리 아래로 이동하여 힙 속성을 복원하는 역할을 합니다. 요소를 자식과 비교하고 필요한 경우 힙 속성이 충족될 때까지 더 큰 자식과 교체합니다.
• push 함수: 이 함수는 우선 순위 큐에 요소를 추가합니다. 요소를 heap 벡터에 추가한 다음 heapifyUp을 호출하여 힙 속성을 유지합니다.
• top 함수: 이 함수는 대기열에서 제거하지 않고 우선 순위가 가장 높은 요소(힙의 루트)를 반환합니다.
• pop 기능: 이 기능은 대기열에서 우선 순위가 가장 높은 요소를 제거합니다. 루트를 벡터의 마지막 요소로 바꾸고 마지막 요소를 제거한 다음 heapifyDown을 호출하여 힙 속성을 유지합니다.
• main 기능: PriorityQueue 클래스의 샘플 사용법입니다. 우선 순위 대기열에 요소를 추가하고 top 및 pop 작업을 사용하여 우선 순위 내림차순으로 인쇄하는 방법을 보여줍니다.

 

 

 

 

 

참고자료

알고리즘 - c++의 priority_queue 사용법

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue)

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)