백준 11279 - 최대 힙

prioirty_queue를 이용해 간단하게 풀 수 있는 문제입니다.

	int cnt;
	std::priority_queue<int, std::vector<int>, std::less<int>> max_queue;

	std::cin >> cnt;

	for (int i = 0; i < cnt; i++)
	{
		int temp;
		std::cin >> temp;

		if (temp == 0)
		{
			if (max_queue.empty())
				std::cout << "0\n";
			else
			{
				std::cout << max_queue.top() << "\n";
				max_queue.pop();
			}
		}
		else
		{
			max_queue.push(temp);
		}
	}

prioirty_queue는 내부적으로 std::make_heap을 이용해 구현되어 있습니다. make_heap은 heapify 알고리즘이며, tree가 heap 조건을 만족하도록 하는 알고리즘입니다.
해당 문제에서는 가장 큰 수가 최상단에 위치해야 하므로 max heap입니다.
heap의 push와 pop을 직접 구현해 해결할 수도 있습니다.

void push(std::vector<int>& vec, int i)
{
	int parent = std::floor((i - 1) / 2);

	if (parent < 0 || i == 0)
		return;

	if (vec[parent] < vec[i])
	{
		int temp = vec[parent];
		vec[parent] = vec[i];
		vec[i] = temp;

		push(vec, parent);
	}
}

void pop(std::vector<int>& vec, int i)
{
	int largest = i;

	int l = i * 2 + 1;
	int r = i * 2 + 2;

	if (l < vec.size() && vec[l] > vec[largest])
		largest = l;
	if (r < vec.size() && vec[r] > vec[largest])
		largest = r;

	if (largest != i)
	{
		int temp = vec[i];
		vec[i] = vec[largest];
		vec[largest] = temp;

		pop(vec, largest);
	}
}

int pop(std::vector<int>& vec)
{
	vec[0] = vec.back();
	vec.pop_back();

	pop(vec, 0);

	return 0;
}

int main()
{
	int cnt;
	std::vector<int> max_heap;

	std::cin >> cnt;

	for (int i = 0; i < cnt; i++)
	{
		int temp;
		std::cin >> temp;

		if (temp == 0)
		{
			if (max_heap.empty())
			{
				std::cout << "0" << "\n";
			}
			else
			{
				std::cout << max_heap.front() << "\n";
				pop(max_heap);
			}
		}
		else
		{
			max_heap.push_back(temp);
			push(max_heap, max_heap.size() - 1);
		}
	}
}