[알골90제] 73/74번 - 최대힙/최소힙 : 우선순위큐

우선순위큐 - 맥스힙 구조 STL 사용

 

최대힙/최소힙 관련 : 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

최대힙

 

최대힙을 사용한 우선순위큐 STL 을 통해 문제를 풀어보자

// 73번 - 최대힙(priority_queue : 우선순위 큐)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
	
	freopen("input.txt", "rt", stdin);
	int a;	//값 읽기
	priority_queue<int> pQ;

	while (true) {
		scanf("%d", &a);
		if (a == -1) break;
		if (a == 0) {
			if (pQ.empty()) printf("-1\n");
			else {
				printf("%d\n", pQ.top());
				pQ.pop();
			}
		}
		else {
			pQ.push(a);
		}
	}
}

 

- a로 값을 읽는다

- priority_queue<int> pQ;  //로 우선순위큐를 선언한다.

- 무한반복문을 열어주고 내부에 조건문을 작성해준다.

while(true) {

}

- a값을 받고, a가 -1이면 break로 반복문을 빠져나간다.

- a값을 받고, a가 0이면 최대힙의 최대값을 꺼낸다

이안에 조건문이 또 들어가는데 empty일 경우 -1을 출력하고

나머지 숫자일 경우 pQ.top(); 을 통해 최대힙의 최대갑을 보여주고, pQ.pop() 해준다.

- -1도 0도 아닌 값이 들어올 경우 최대힙에 값을 계속 넣어줘야 한다. pQ.push(a); 를 통해.

 

 

최소힙

 

최소힙은 단순히 최대힙에서 값을 넣어줄때 -만 넣어주면된다. 그리고 출력할때 다시 -를 붙여서 출력해준다.

//74번 - 최소힙 우선순위큐

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
	
	freopen("input.txt", "rt", stdin);
	int a;
	priority_queue<int> pQ;

	while (true) {

		scanf("%d", &a);
		if (a == -1) break;
		if (a == 0) {
			if (pQ.empty()) printf("-1\n");
			else {
				printf("%d\n", -pQ.top());
				pQ.pop();
			}
		}
		else {
			//push할때 부호를 바꿔서 넣으면 최소힙됨
			pQ.push(-a);
		}
	}
}