🙇‍♀️최대힙(priority_queue : 우선순위 큐)

최대힙은 완전이진트리로 구현된 자료구조입니다.

그 구성은 부모 노드값이 왼쪽자식과 오른쪽 자식노드의 값보다 크게 트리를 구성하는 것입니다.

그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 큰 값이 저장되어 있습니다.

예를 들어 5 3 2 1 4 6 7순으로 입력되면 최대힙 트리는 아래와 같이 구성됩니다.

image

최대힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요.

1) 자연수가 입력되면 최대힙에 입력한다. 2) 숫자 0 이 입력되면 최대힙에서 최댓값을 꺼내어 출력한다. (출력할 자료가 없으면 -1를 출력한다.) 3) -1이 입력되면 프로그램 종료한다.

▣ 입력설명
첫 번째 줄부터 숫자가 입력된다. 

입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정수형 범위에 있다.

▣ 출력설명
2) 연산을 한 결과를 보여준다.

🚀풀이

우선순위 큐를 구현해서 푸는게 아니라 사용법을 익히는 문제이다.

그래서 바로 코드!

priority_queue<int, vector<int>> q;
void solve()
{
	int temp = 123456789;
	while (true)
	{
		cin >> temp;
		if (temp == -1)
			break;
		if (temp == 0)
		{
			if (q.size() == 0)
			{
				cout << -1 << '\n';
			}
			else
			{
				int t = q.top();
				cout << t << '\n';
				q.pop();
			}
		}
		else 
			q.push(temp);
	}
}

우선순위 큐의 두 번째 인자는 컨테이너고 세 번째 인자는 정렬 방식을 선택한다.

큰 값부터 나오게 할려면 less<int>로 하면된다.

기본적으로는 less<int>상태이다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

priority_queue<int, vector<int>> q;
void solve()
{
	int temp = 123456789;
	while (true)
	{
		cin >> temp;
		if (temp == -1)
			break;
		if (temp == 0)
		{
			if (q.size() == 0)
			{
				cout << -1 << '\n';
			}
			else
			{
				int t = q.top();
				cout << t << '\n';
				q.pop();
			}
		}
		else 
			q.push(temp);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고