[자료구조] 백준 1927번: 최소 힙

출처: https://www.acmicpc.net/problem/1927

 

출처: https://www.acmicpc.net/problem/1927

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int heap[100001];
int t = 0;
int n;

void swap(int i, int j)
{
	int tmp = heap[i];
	heap[i] = heap[j];
	heap[j] = tmp;
}

//값 저장
void push(int x)
{
	heap[++t] = x;

	for (int i = t; i > 1; i /= 2)
	{
		if (heap[i] < heap[i / 2])
			swap(i, i / 2);
		else
			break;
	}
}

//내림차순으로 값 출력
int pop()
{
	int top = heap[1];
	heap[1] = heap[t];
	heap[t--] = 0;

	int i = 1;
	while (i * 2 <= t)
	{
    	//자식이 하나일 때
        if (heap[i * 2 + 1] == 0)
		{
			if (heap[i] < heap[i * 2])
				break;
			else if (heap[i] > heap[i * 2])
			{
				swap(i, i * 2);
				i = i * 2;
			}
			else
				break;
		}
        //자식이 둘일때
		else
		{
			if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1])
				break;
			else if (heap[i * 2] <= heap[i * 2 + 1])
			{
				swap(i, i * 2);
				i = i * 2;
			}
			else if(heap[i * 2] >
				heap[i * 2 + 1])
			{
				swap(i, i * 2 + 1);
				i = i * 2 + 1;
			}
			else
				break;
		}
	}
	return top;
}

int main()
{
	int x;

	scanf("%d", &n);
	while (n--)
	{

		scanf("%d", &x);
		if (x == 0)
		{
			if (t == 0)
				printf("0\n");
			else
				printf("%d\n", pop());
		}
		else
			push(x);
	}
	return 0;
}