Priority Queue (우선순위큐)

heap 구조

- 현재 우선순위 큐 안에서 제일 우선순위가 높은 원소가 pop됨

- 주요 명령어 : push, pop, top

- Heap 을 이용해서 구현

       - heap 은 트리 구조로 되어있다. (노드들로 구성되어있으며, 각 노드는 부모-자식 관계로 이루어져 있다.)

       - max heap : 숫자가 클 수록 우선순위가 높다.

       - min heap : 숫자가 작을 수록 우선순위가 높다.

- 삽입/삭제 : O(logN)

 

c++ 에서 priority queue는 max heap으로 구성된다.

min heap으로 구성하기 위해서는 greater<> 을 사용하여 정렬하면 된다.

 

- max heap priority queue 선언

          priority_queue <int> pq;

- min heap priority queue 선언

          priority_queue <int, vector<int>, greater<int>> pq;

 

 

- pair 형태의 priority queue를 min heap으로 만들기

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;