(TIL) C++ Priority Queue ~

우선순위큐의 추상 데이터 타입

우선순위 큐는 지금까지 배운 자료구조들과 다르게 위치 기반 저장을 하지 않는다. 각 원소에 우선순위값(키값)이 있고 그 우선순위에 따라 정렬된 순서로 삽입되고 삭제된다.

Totla order로 키 비교하기

우선순위큐가 정의되기 위해서는 total order 관계라는 것을 정의해야 한다. 모든 한 쌍의 키들은 다음과 같은 속성을 지녀야 한다.

반사성: k <= k 비대칭성: if k1 <= k2 and k2 <= k1, then k1 = k2 이행성: if k1 <= k2 and k2 <= k3, then k1 <= k3

---

우선순위큐에는 가장 기본적인 연산 세 가지가 있다.

insert, min, removeMin이 그것인데 위의 total order 관계에 의하면 최소키가 여러 개가 있을 수 있다. 그래서 min 연산을 정의할 때 언제나 같은 값이 나오도록 적절히 정의해야 한다.

원소들 간에 우선순위를 결정하기 위해 비교를 하는 방법은 여러가지가 있다. 첫 번째 방법으로는 컴포지트 메서드를 사용하는 것인데 키와 값을 하나로 묶는 것이다. 이렇게 되면 원소를 직접 읽을 필요도 없이 키끼리만 비교하면 된다. 두 번째 방법은 부등호 연산자를 오버로딩하여 원소 간의 우선순위를 정의하는 것이다. 세 번째 방법은 비교자 클래스를 정의하여 () 연산자를 오버로딩하여 두 원소를 비교하게 하는 것이다. 세 번째 방법의 예시 코드는 다음과 같다.

class LeftRight { // a left-right comparator
public:
bool operator()(const Point2D& p, const Point2D& q) const
{ return p.getX() < q.getX(); }
};

class BottomTop { // a bottom-top comparator
public:
bool operator()(const Point2D& p, const Point2D& q) const
{ return p.getY() < q.getY(); }
};

우선순위큐를 통해 리스트를 정렬할 수도 있다. 리스트의 원소들을 모두 우선순위큐에 집어넣은 다음 min()과 removeMin() 연산을 통해 최소값을 계속 추출하여 리스트에 순서대로 집어넣는 것이다. 이렇게 하면 키에따라 오름차순으로 정렬된 리스트를 얻을 수 있다.

STL에는 이미 우선순위큐가 구현되어 있다. 사용하려면 다음과 같이 하면 된다.

#include <queue>
using namespace std; // make std accessible

priority_queue<int> p1; // a priority queue of integers

// a priority queue of points with left-to-right order

priority_queue<Point2D, vector<Point2D>, LeftRight> p2;

오늘은 여기까지…. 내일부터는 우선순위 큐 구현부터 들어간다. 요즘 프로젝트에 힘을 쏟다보니 오전에 하는 공부에 집중력이 떨어지는 것 같다.