[C++] STL 우선순위 큐 (priority_queue)

우선순위 큐란?

기존 큐는 넣은 순서대로 빠지는 반면, 우선순위 큐는 넣는 것은 동일하지만 빠지는 건 최소 또는 최대부터 빠진다.

여기서 최대부터 빠지는 걸 Max Heap이라 칭하고, 최소부터 빠지는 걸 Min Heap이라고 칭한다.

우선순위 큐의 작동원리

Max Heap과 Min Heap은 자료구조 시간에 배운 기억이 난다.

 

출처) http://i-bada.blogspot.com/2012/05/heap-maxmin-heap.html

다음 그림을 보면 더 생각이 잘 날것이다.

 

• 우선순위 큐는 자료구조 상 배열, 연결리스트, 힙으로 구현이 가능하다.(따라서 백터와 덱 컨테이너와 붙어서 사용이 가능하다 - 리스트 불가능)

• 내부적으로 <algorithm>에 있는 힙 관련 함수들을 사용하여 구현되어있다.

• 내부구조는 default로 vector container 기반으로 설정되어 있다.

• 정렬기준 default는 내림차순(less) 기반으로 설정되어 있다.

우선순위 큐의 선언&기본 함수

선언

#include <queue>

priority_queue<T, Container, Compare>

 

* 우선순위를 내림차순으로 설정
priority_queue<int> q;
priority_queue<int, vector<int>,less<int> > q;

 

* 우선순위를 오름차순으로 설정
priority_queue<int, vector<int>,greater<int> > q;

 

less가 단어 의미상 작은 것부터지만, 나오는 건 큰것부터고
greater는 '보다 큰' 이란 뜻이지만, 나오는 건 작은것부터입니다.

 

기본 함수

• q.push(element)

• q.top() - q.front()가 아니다!!!

• q.size()

• q.pop()

• q.empty()