우선순위 큐 STL 사용법

우선순위 큐
기존 큐가 넣은 순서대로 빠지는 반면, 우선순위 큐는 넣는 건 동일하되,
빠지는 건 최소, 혹은 최대부터 빠집니다.

최대부터 빠지는 걸 Max Heap, 최소부터 빠지는 걸 Min Heap이라고 합니다.

단점이라면, 현재 넣은 수들의 최대 혹은 최소밖에 모르는 단점이 있습니다만,
이걸 이길 정도로 꽤 쓸만한 녀석입니다.

선언은 아래와 같이 합니다.

그림1

위의 두개에 대한 경우 int에 대한 Max Heap, 밑은 Min Heap 입니다.

잘 보실 게 있는데, less가 단어 의미상 작은 것부터지만, 나오는 건 큰것부터고
greater는 '보다 큰' 이란 뜻이지만, 나오는 건 작은것부터입니다. 
이건 외워두시면 됩니다. 왜인지는 잘 모르겠지만요.

여튼. 잘 쓰는 메서드는 5가지가 있습니다.

그림2

q.push(value); - 큐에 값을 넣습니다. 간단하죠?

q.top(); - min heap은 큐에서 가장 작은 값, max heap은 큐에서 가장 큰 값을 리턴합니다. 

q.size(); - 큐에 몇개가 들어있는지 리턴합니다.

q.empty(); - 큐에 1개라도 들어있으면 true, 아무것도 없으면 false를 리턴합니다.

q.pop(); - min heap은 큐에서 가장작은 값, max heap은 큐에서 가장 큰 값을 큐에서 제거합니다.



간단히 사용법에 대해서만 알아보았습니다.


출처> http://dyngina.tistory.com/24