우선순위 큐(priority_queue) 최대 힙, 최소 힙 in C++ - (1)

1. 우선순위 큐를 이용한, 최대값 출력(최대 힙)

-1을 입력으로 주면, 해당 프로그램을 종료한다.
0을 입력으로 주면, 해당 프로그램 진행중에 나온 최대값을 출력하고, 해당 값을 우선순위 큐에서 삭제한다.
0을 입력으로 주었을때, 우선순위 큐가 비어있다면 -1을 출력한다.

#include <iostream>
#include <queue>

using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	priority_queue<int> pQ;
	
	while(true) {
		int temp;
		cin >> temp;
		if(temp == -1) break;
		if(temp == 0) {
			if(pQ.empty()) cout << -1;
			else {
				cout << pQ.top() << "\n";
				pQ.pop();
			}
		}
		else pQ.push(temp);
	} 
	return 0;
}

• priority_queue : 우선순위 큐를 선언하는 부분이다.
• empty : 우선순위 큐가 비어있는지 확인하는 역할을 한다.
• top : 우선순위 큐 트리에서 최상단에 있는 값, 즉 최대 값을 가리킨다.
• pop : 우선순위 큐 트리에서 최상단에 있는 값, 즉 최대 값을 큐에서 제거한다.
• push : 우선순위큐에 원소를 상입하는 역할을 한다.

ex) 입력이 다음과 같을때의 출력
1 2 3 4 5 0 0 7 8 9 0 -1

2. 우선순위 큐를 이용한, 최소값 출력(최소 힙)

입력과 출력시에 -를 붙여주면, 최소힙을 사용하여 최소값을 출력하는 것과 같은 결과를 얻을 수 있다.

#include <iostream>
#include <queue>

using namespace std;
int main() {
	freopen("input.txt", "rt", stdin);
	priority_queue<int> pQ;
	
	while(true) {
		int temp;
		cin >> temp;
		if(temp == -1) break;
		if(temp == 0) {
			if(pQ.empty()) cout << -1;
			else {
				cout << -pQ.top() << "\n"; // -
				pQ.pop();
			}
		}
		else pQ.push(-temp); // -
	} 
	return 0;
}

ex) 입력이 다음과 같을때의 출력
1 2 3 4 5 0 0 7 8 9 0 -1