minjgziii

💡 우선순위 큐

• 오름차순과 내림차순과 같은 정렬 기능이 들어간 queue
• 우선순위 큐는 각 원소들이 우선순위를 갖는다.
• priority_queue는 기본적으로 내림차순으로 정렬
• priority_queue<자료형, 구현체, 비교연산자>
• 비교 연산자에는 less<자료형>, greater<자료형>이 있음
  • less : 내림차순 ( 큰 -> 작은)
  • greater : 오름차순 ( 작은 -> 큰)

오름차순 정렬을 위해서는 다음과 같이 정렬해야 한다.

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

아래의 두 가지 코드는 같다.

priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;

operator < 를 사용

💡 우선순위 큐 구현하는 방법

• 배열
• 링크드 리스트
• 힙

힙으로 우선순위 큐를 구현하는데 가장 효과적이고, STL 또한 priority_queue는 make_heap 기반으로 구현되어 있다.

💡 make_heap

C++ heap의 헤더파일은 <algorithm>에 정의되어 있다.

STL에서도, make_heap은 힙이라는 container를 제공해 주는 것이 아니라 사용자의 vector를 인자로 받아 힙 구조로 변환 시켜 준다.

vector를 make_heap을 통해 힙을 구성하면, 우선순위가 가장 높은 데이터는 첫번째 Index에 위치하게 된다. 그리고, 나머지 요소는 heap에 맞는 구조를 띄게 된다.

데이터 우선순위를 재정의 해 주지 않으면 기본적으로 max_heap으로 구성된다.

요약하자면,

• make_heap : comp는 생략하면 기본적으로 operator< 함수를 사용하여 max_heap을 구성
• priority_queue : 내부적으로 make_heap을 사용하는데 이 container에도 comp를 생략하면 less Class를 사용해 make_heap의 인자로 operator < 를 넘겨주는 것과 동일한 역할을 수행하게 된다.

🧐 참고 사이트