우선순위 큐 Priority Queue C++

개요

1. Queue

일반적인 큐의 경우 선입 선출을 통해 먼저 들어왔던 데이터가 먼저 처리되는 특성을 가진다.

큐 내에 {1, 2, 3, 4, 5} 가 존재한다면, 6을 push하고 front에 존재하는 값을 pop 한다면 {2, 3, 4, 5, 6}이 되고, 6을 사용하기 위해선 앞에 존재하는 2, 3, 4, 5가 모두 pop 되어야 6을 pop 할 수 있다.

 

2. Priority Queue

기본적인 큐에서 특정 조건으로 인해 큰 값으로 정렬 되어 있는 큐이다.

만약 큐에 {5, 4, 3, 2, 1}이 존재한다고 가정했을때 6을 push한 후 front에 존재하는 값을 pop 한다면, 6이 pop이 될 것이다.

pq의 기본형은 내림차순 정렬이지만, 특정 compare 함수를 작성할 경우 우선순위를 다양하게 설정할 수 있다.

 

입력

priority_queue<int> pq;
pq.push(21);
pq.push(13);
pq.push(7);
pq.push(16);
pq.push(42);
pq.push(1);
pq.push(15);
cout << pq.top();

 

출력

42

 

 

일반적인 큐를 사용했을 경우 21이 출력 됐을 것이다, 하지만 현재 pq가 정수형 내림차순으로 정렬되도록 형태를 띄고 있기 때문에 5번째로 pq에 push 되었지만 다른 값들과 비교하여 가장 큰 값인 42가 출력된다.

 

이는 우선순위 큐에 데이터를 저장하는 구조가 기본적으로 MAX HEAP 트리로 이루어 져 있기 때문이다.

 

Completely binary tree

Completely binary tree 예시

 

vector을 사용해 인자를 정렬해도 되지만, 데이터의 삽입, 삭제가 빈번한 경우 매번 정렬 작업을 해주게 될 경우 불 필요한 작업으로 인해 시간 복잡도의 영향을 많이 받게 된다.

 

pq에서는 기본적으로 vector을 사용하는 구조이긴 하나 트리 형태를 통해 모든 노드에 대해 정렬 작업해 주지 않고, 필요한 사이드의 노드들만 정렬 작업을 해주기 때문에 매번 정렬 작업을 진행하는 것에 비해 시간 복잡도 상에서 이득을 취할 수 있다.

 

vector를 정렬할 경우 모든 요소를 체크해야 하기에 O(NLogN)의 시간 복잡도를 갖지만, pq의 경우 O(logN)의 시간 복잡도를 갖는다. N배 차이, N이 10만일 경우 10만배 차이가 나는 수준이다.

 

자식 노드는 최대 2개를 가질 수 있으며, 왼쪽부터 먼저 채우는 트리 형태이다.

직접 연결된 노드간의 우선 순위가 있으며, 우선 순위 대로 데이터를 관리하는 밸런싱을 맞추는 작업을 동시에 처리한다.

 

pq 관련 메서드들

• push(val) : 큐에 새로운 원수를 추가, 큐는 힙 구조를 유지
• pop() : 큐의 맨 앞에 있는 원소를 제거, C++ 에서는 파이썬 처럼 pop과 동시에 원소를 반환하지 않으므로 값을 얻기 위해서는 top()을 먼저 호출해 주어야 한다.
• top() : 우선 순위에 따라 관리 된 맨 앞 노드(ROOT 노드) 확인
• empty() : 큐가 비어있는지 확인한다, 비어 있으면 true, 그렇지 않으면 false를 반환한다.
• size() : 큐에 있는 원소의 개수를 반환한다.

pop의 원리

작동하는 것을 보면 root를 바로 확인하고 삭제하는 것으로 보이나, 트리 입장에서 루트 노드를 바로 제거하면 데이터의 형태가 깨지게 된다.

그러므로, pop을 수행하게 되면 가장 리프 노드의 오른쪽에 있는 값이 root노드로 대체되고, 기존에 있던 자리의 노드가 삭제되게 된다. 이후 루트 노드의 하위 자식 노드 중 큰 값과 비교하여 자리를 교체하고 마찬가지로 하위 노드와 비교하여 더 큰 값이 있을 경우 자리를 교체해 우선 순위 대로 데이터를 관리하는 밸런싱을 잡아주게 된다.

 

3. PQ의 구조

Visual Studio 우선순위 큐의 정보

컨테이너 어답터 (Container Adapter)

자체적으로 데이터를 저장하는 container가 있는 것이 아니라, 저장하는 건 vector로 되어 있고, vector를 우선 순위에 맞춰서 관리하는 구조이다.

그래서 pq는 첫번째 인자로는 인자로 받을 요소들의 타입, 두번째 인자로는 해당 인자들을 저장하는 데 사용할 자료구조와 타입(기본 값은 벡터로 설정되어 있다.), 세번째 인자로 해당 요소들을 정렬할 우선 순위 조건을 넣어주게 된다.

우선 순위 조건이 기본적으로는 less로 되어 있는 것을 확인할 수 있다.  

less 구조체

less를 찾아가 보면 left보다 right가 큰지를 bool 값으로 return하고 있다. 이를 참고하면 return 값이 true라면 내림 차순을 정렬한다는 말이다.

 

만약 리턴의 부동호가 바뀐 경우에는 어떻게 될까? pq는 내림 차순이 아닌 오름 차순으로 정렬된 큐를 갖게 될것이다.

이 처럼 pq는 커스텀 함수를 제작하여 별도의 정렬 우선순위 조건을 세팅할 수 있다.

 

예제

1. operator 오버로딩을 통한 정렬

구조체 내부에 연산자 오버로딩을 통해 커스텀 비교 함수를 작성한다. 만약 현재 row가 오른쪽에 있는 요소의 row보다 클 경우 return true 즉, 자리를 바꿔주고, 작을 경우 자리를 바꿔주지 않는다, 같을 경우 col을 비교하여 col이 더 클 경우 바꿔주고 작거나 같을 경우 자리를 바꿔주지 않는다.

 

이는 정렬에 사용하는 커스텀 비교 함수와는 반대로 작동한다. sort는 기본 정렬값이 오름차순이며 pq는 기본 정렬값이 내림차순 정렬이기 때문이다.

즉, pq와 sort에서 사용하는 정렬은 반대로 만들어 주어야 한다.

 

코드

#include<iostream>
#include<queue>

using namespace std;

struct Coord {
	int row, col;
	bool operator<(const Coord& right) const {
		if (row > right.row) return true;
		if (row < right.row) return false;
		return col > right.col;
	}
};

priority_queue<Coord, vector<Coord>> pq;

int main() {
	pq.push({ 1, 4 });
	pq.push({ 4, 7 });
	pq.push({ 4, 3 });
	pq.push({ 2, 6 });
	pq.push({ 3, 1 });
	while (!pq.empty()) {
		Coord cur = pq.top(); pq.pop();
		cout << "(" << cur.row << ", " << cur.col << ")\n";
	}
}

 

출력

(1, 4)
(2, 6)
(3, 1)
(4, 3)
(4, 7)

 

2. 커스텀 객체를 통한 정렬

pq의 타입으로 사용할 객체 외에 커스텀 함수를 실행할 구조체를 정의한 후 3번째 인자로 해당 객체를 인자로 전달해 준다면 커스텀 함수처럼 사용할 수 있다.

 

코드

#include<iostream>
#include<queue>

using namespace std;

struct Coord {
	int row, col;
};

struct cmp_coord {
	bool operator()(const Coord& left, const Coord& right) const {
		if (left.row > right.row) return true;
		if (left.row < right.row) return false;
		return left.col > right.col;
	}
};

priority_queue <Coord, vector<Coord>, cmp_coord> pq;

int main() {
	pq.push({ 1, 4 });
	pq.push({ 4, 7 });
	pq.push({ 4, 3 });
	pq.push({ 2, 6 });
	pq.push({ 3, 1 });
	while (!pq.empty()) {
		Coord cur = pq.top(); pq.pop();
		cout << "(" << cur.row << ", " << cur.col << ")\n";
	}
}

 

출력

(1, 4)
(2, 6)
(3, 1)
(4, 3)
(4, 7)