우선순위 큐(Priority Queue)

개요

---

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식의 자료구조이다.

우선순위 큐는 먼저 들어온 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

일반적으로 힙을 이용해 구현한다.

C++에서 우선순위 큐

---

C++에서는 <queue> 라이브러리를 통해 우선순위 큐를 사용할 수 있다. 기본적으로 최대 힙으로 구현되어 있으며, std::priority_queue 클래스를 사용한다.

내부적으로 std::vector를 기본 컨테이너로 사용하여 연속된 메모리 공간에 데이터를 저장한다.

메서드

• push(value) : 원소를 복사/이동하여 삽입 후 힙 재정렬. O(log N)
• emplace(args...) : 임시 객체 생성 없이 내부 메모리에서 직접 객체를 조립하여 삽입. O(log N)
• pop() : 최상위 원소 제거 (값 반환 X). O(log N)
• top() : 최상위 원소의 참조값 반환. O(1)
• empty() : 큐가 비어있는지 여부 반환. O(1)
• size() : 큐에 저장된 원소의 개수 반환. O(1)

선언 양식 및 타입 커스텀

std::priority_queue의 템플릿 인자는 총 3개이다.

std::priority_queue<T, Container, Compare>

• T : 저장할 데이터 타입
• Container : 내부 컨테이너 타입 (기본값은 std::vector<T>)
• Compare : 우선순위 비교 구조체/함수 (기본값은 std::less<T>)

만약 최대 힙(내림차순)으로 선언하고 싶다면

// 둘은 같은 선언임
std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::less<int>> maxHeap;

최소 힙으로 선언하고 싶다면 아래처럼 하면 된다.

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

알고리즘 문제를 풀다 보면 X좌표가 작고 Y좌표가 큰 순같이 정렬할 일이 많은데, 구조체 연산자 오버로딩을 통해 할 수 있다.

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        if (y != other.y)
        {
            return y < other.y; // Y좌표가 큰 순
        }
        return x > other.x; // X좌표가 작은 순
    }
};

std::priority_queue<Point> pq;

추가로 이미 데이터가 다 쌓여있는 배열이 있을 때, 반복문으로 하나씩 push하면 O(N log N)이 걸리지만, 벡터의 반복자 범위를 우선순위 큐 생성자에 통째로 넘겨주면 내부적으로 하단 서브트리부터 역순으로 힙을 만드는 과정을 거쳐 O(N) 시간에 힙을 만들 수 있다.

std::vector<int> data = {5, 3, 8, 1, 4};
std::priority_queue<int> pq(data.begin(), data.end());

참고

• https://suyeon96.tistory.com/31
• https://sechoi.tistory.com/36