[c++] priority_queue

c++에서 priority_queue는 max heap 개념입니다. 가장 큰 요소가 항상 맨 위 위치에 있도록 해당 요소를 정렬합니다.

항상 가장 크거나 우선 순위가 가장 높은 일부 기본 컨테이너 형식의 최상위 요소에 대한 액세스를 제한하는 기능 제한을 제공하는 템플릿 컨테이너 어댑터 클래스입니다. 새 요소를 추가할 priority_queue 수 있으며 해당 요소의 priority_queue 최상위 요소를 검사하거나 제거할 수 있습니다.

 

1. 클래스 헤더 파일

#include <queue>

2.클래스 원형

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

priority_queue <T,vector<T>,compare> pq;    // T : 구조체

3. Parameter (매개 변수)

Type	priority_queue에 저장되는 요소 데이터 형식
Container	priority_queue를 구현하는데 사용되는 기본 컨테이너의 형식
Compare	두 요소 값을 정렬 키로 비교하여 해당 요소의 상대 순서를 확인할 수 있는 함수 개체를 제공하는 형식. 이 인수는 선택 사항. 기본 값은 이진 조건자 less<typename Container::value_type>

 

 

4. Member Function

멤버 함수	Description
empty	priority_queue 가 비어 있는지 확인(테스트)합니다.
pop	가장 큰 요소를 최상위 위치를 제거합니다.
push	"operator<"에서 요소의 우선 순위에 따라 우선 순위 큐에 요소를 추가합니다.
size	priority_queue 에 있는 요소 수를 반환합니다.
top	priority_queue의 최상위 위치에 있는 가장 큰 요소에 대한 const 참조를 반환합니다.

 

5. Example

(1)

	priority_queue<int, deque<int>> pq;

	pq.push(5);
	pq.push(15);
	pq.push(10);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

15 10 5

(2)

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

	pq.push(5);
	pq.push(15);
	pq.push(10);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

5 10 15

(3)

	priority_queue<int> pq;

	pq.push(5);
	pq.push(15);
	pq.push(10);

	priority_queue<int> pq2(pq);

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}

15 10 5

(4)

priority_queue는 기본으로 내림차순 정렬입니다. 

나이 내림차순, 나이가 같다면 알파벳 내림차순으로 정렬하도록 compare함수를 정의합니다.

using namespace std;

struct Person {
	int age;
	string name;
	Person(int a, string b) : age(a), name(b) {}
	bool operator<(const Person& b)const {
		if (age == b.age) {
			return name < b.name;
		}
		return age < b.age;
	}
};

int main(int argc, char** argv)
{
	priority_queue<Person> pq;

	pq.push(Person(20, "AAB"));
	pq.push(Person(15, "BCD"));
	pq.push(Person(15, "ABC"));
	pq.push(Person(20, "AAC"));
	pq.push(Person(20, "AAA"));
	
	while (!pq.empty())
	{
		auto& [n, str] = pq.top();
		cout << n << " " << str << endl;
		pq.pop();
	}

	return 0;
}

20 AAC
20 AAB
20 AAA
15 BCD
15 ABC

compare구조체를 새로 만들어서 하는 방법입니다.

struct Person {
	int age;
	string name;
};

struct cmp {
	bool operator()(Person& a, Person& b) {
		if (a.age != b.age) {
			return a.age < b.age;
		}
		return a.name < b.name;
	}
};