priority_queue

우선순위가 높은 요소가 먼저 나오는 큐
일반 큐(FIFO)와 달리 삽입 순서가 아닌 우선순위에 따라 요소가 처리

내부 구조

• Priority Queue는 내부적으로 Heap으로 구현
• Max Heap : 큰 값이 높은 우선순위 (기본값)
• Min Heap : 작은 값이 높은 우선순위

삽입과 삭제가 빈번하면서 최댓값/최솟값 조회가 필요한 경우 최적

주요 멤버함수

1. 생성자 / 초기화

#include <iostream>
#include <queue>
#include <vector>
#include <list>

int main()
{
	// 1. 기본 생성자 - Max Heap
	std::priority_queue<int> q1;

	// 2. 비교자(Comparator) 지정
	// 형식 : priority_queue<타입, 컨테이너, 비교자>
	std::priority_queue<int, std::list<int>, std::less<int>> q2;
	// 컨테이너 - 기본 std::vector
	// 비교자 - 우선순위 결정(기본 : std::less = Max Heap)

	// 3. 범위로 초기화(반복자)
	// 벡터로 초기화 (Max Heap)
	std::vector<int> v1 = { 4,6,7,4,73,4,6,7,35,1,23,3 };
	std::priority_queue<int> q3(v1.begin(), v1.end());

	// 4. 사용자 정의 비교자
	// 람다 함수 비교 첫번째가 2로나눴을때 나머지가 0일경우 우선, 아닐경우 값이 큰쪽
	auto fob1 = [](int a, int b) {
		if (a % 2 == 0)
			return true;
		else
			return a > b; };
	std::priority_queue<int, std::vector<int>, decltype(fob1)> q4(fob1);

	// 5. 복사 생성자
	std::priority_queue<int> q5 = q3; // or std::priority_queue<int> q5(q3)
	//    복사 대입 연산자
	std::priority_queue<int> q6;
	>
	// 6. 이동 생성자
	std::priority_queue<int> q7 = std::move(q6);
	//    이동 대입 연산자
	std::priority_queue<int> q8 = std::move(q7);

	// 7. 컨테이너 기반 생성자
	std::vector<int> v2 = { 4,6,7,4,73,4,6,7,35,1,23,3 };
	std::priority_queue<int> q9(std::less<int>(), v2);
	return 0;
}

2. 접근자

#include <iostream>
#include <queue>
#include <vector>
#include <list>

int main()
{
	// top() - 최상위 원소(우선순위가 가장 높은 원소)를 반환
	std::vector<int> v1 = { 4,6,7,4,73,4,6,7,35,1,23,3 };
	std::priority_queue<int> q1(v1.begin(), v1.end());

	std::cout << q1.top() << std::endl; // 73 
	// 우선순위 큐는 힙(heap) 구조로 구현되어 있어
	// 최상위 원소 외의 다른 원소들은 정렬되어 있지 않다.
	// 중간 원소에 접근하는 것이 의미가 없고, 구조를 유지하기 위해 접근을 제한

	return 0;
}

3. 요소 추가/삭제

#include <iostream>
#include <queue>
#include <vector>
#include <string>

int main()
{
	std::priority_queue<std::pair<int,std::string>> q1;

	// push() - 원소를 복사 또는 이동해서 삽입
	// push : 객체 생성 → 복사/이동
	std::pair<int, std::string> pair1 = { 1,"감자" };
	q1.push(pair1); // 복사
	q1.push(std::move(pair1)); // 이동 ==  q1.push({ 1,"감자" }); - 임시 객체 생성후 이동

	// emplace() - 원소를 제자리에서 직접 생성
	// emplace : 내부에서 직접 생성 
	q1.emplace(2,"튀김");

	// pop() - 최상위 원소(우선순위가 가장 높은 원소) 제거
	q1.pop(); // 2, 튀김 삭제

	std::cout << q1.top().first << ", " << q1.top().second << std::endl; // 1 , 감자

	return 0;
}

4. 용량 / 교환

#include <iostream>
#include <queue>
#include <vector>
#include <string>

int main()
{
	std::vector<int> v1 = { 4,6,6,32,21,1,52,3,5,64,643 }; 
	std::priority_queue<int> q1(v1.begin(),v1.end());
	std::priority_queue<int> q2;
	q2.push(5);

	// size() - 요소 개수 반환
	// 반환값 : size_t (부호 없는 정수)
	size_t size = q1.size();  // 11개

	std::cout << size << std::endl;

	// empty() - 큐가 비어있는지 확인
	// 반환값 : bool
	bool isempty = q1.empty(); // false(0)

	std::cout << isempty << std::endl;

	// swap() - 두 우선순위 큐의 값 교환(같은 타입)
	q2.swap(q1);

	std::cout << q1.top() << std::endl; // 교환후 최상위원소 5 출력
	std::cout << q2.top() << std::endl; // 교환후 최상위원소 643 출력

	return 0;
}