[알고리즘] 구조체 Priorty Queue / C++

우선순위 큐 자료구조를 이용할 때, 구조체를 이용할 때가 있는데 이럴 땐 어떻게 큐를 정의하는 지 살펴보자.

 

기본 자료형

sort와 같은 방식으로, greater, less를 이용한다.

priority_queue<int, vector<int>, greater<int>> pq; // 오름차순

주의할 점은 algorithm 내 sort의 greater은 내림차순이고,
우선순위 큐의 sort의 greater은 오름차순이다.

 

구조체

이번에는 compare 구조체를 만들어서 대소비교하는 operator 함수를 오버로딩한다.
여기서 주의해야할 점은 인자의 순서다.
right, left 순서로 정의해 주어야 한다.

struct compare {
	bool operator()(const Struct right, const Struct left) {
		return s1.value < s2.value;
	}
};

priority_queue<Struct, vector<Struct>, compare> pq;

 

우선순위 큐의 특징

1. 완전 이진트리 형태의 힙을 이용해 구현한다.
2. 삽입과 삭제는 O(logN)의 시간복잡도를 가진다.
3. 정렬은 O(N*logN)의 시간복잡도를 가진다.

 

Sort vs Priorty Queue

Sort 와 Priorty Queue큐 중 어떤 것을 써야할까?

Sort 이용시 최악의 경우 시간복잡도가 O(N^2)이기 때문에 Priority Queue가 더 낫지 않을까 생각한다.
다음의 외부 포스팅을 참고해보면 실제로 테스트 결과 퀵소트보다 Priority Queue가 더 빠르다는 것을 확인할 수 있다.

퀵 소트와 Priority Queue와의 속도 비교 테스트