[11279] C++ : 최대 힙

이 문제는 최소 힙에서 부등호만 바꾸면 된다.

2022.08.16 - [Programming/백준] - [1927] C++ : 최소 힙

[1927] C++ : 최소 힙

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제 출력 1 

0
2
1
3
2
1
0
0

 

풀이

#include<iostream>

using namespace std;


int arr[100001] = { 0 };

void insert(int data, int* count)
{
	arr[++(*count)] = data;

	for (int i = (*count); i > 1; i /= 2)
	{
		if (arr[i] > arr[i / 2])
		{
			int temp = arr[i];
			arr[i] = arr[i / 2];
			arr[i / 2] = temp;
		}
	}
}

void delete_heap(int* count)
{
	cout << arr[1] << "\n";

	arr[1] = arr[(*count)];
	arr[(*count)] = 0;
	(*count)--;

	for (int i = 1; (i <= (*count / 2)) && (i * 2 + 1 <= 100001);)
	{

		if ((arr[i * 2 + 1] == 0))
		{
			if (arr[i] <= arr[i * 2])
			{
				int temp = arr[i];
				arr[i] = arr[i * 2];
				arr[i * 2] = temp;
				i = i * 2;
			}

			break;
		}

		if ((arr[i] < arr[i * 2])) 
		{
			if (arr[i * 2] > arr[i * 2 + 1]) 
			{
				int temp = arr[i];
				arr[i] = arr[i * 2];
				arr[i * 2] = temp;
				i = i * 2;
			}
			else 
			{
				int temp = arr[i];
				arr[i] = arr[i * 2 + 1];
				arr[i * 2 + 1] = temp;
				i = (i * 2 + 1);
			}

		}
		else if (arr[i] < arr[i * 2 + 1]) {
			int temp = arr[i];
			arr[i] = arr[i * 2 + 1];
			arr[i * 2 + 1] = temp;
			i = (i * 2 + 1);
		}
		else
			break;
	}

}

int main(void)
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	int number, repeat;
	int count = 0;
	cin >> repeat;

	for (int i = 0; i < repeat; i++)
	{
		cin >> number;
		if (number == 0)
		{
			if (count == 0)
				cout << 0 << "\n";
			else
				delete_heap(&count);
		}
		else
		{
			insert(number, &count);

		}
	}
	return 0;
}