<백준> 11279 최대 힙

https://www.acmicpc.net/problem/11279

 

간단한 최대 힙 구현 문제이다.

left 인덱스 범위 설정 해주는 부분에서 계속 헷갈리는듯

ios::sync_with_stdio(false) 안해주면 시간초과 난다... 왜 그럴까

#include<iostream>
#include<vector>

using namespace std;

vector<int> v;

class heap
{
public:
	heap()
	{
		v.push_back(0);
	}
	void max()
	{
		if (v.size()==1)
		{
			cout << "0";
			return;
		}
		cout << v[1];
		v[1] = v[v.size() - 1];
		v.pop_back();
		int idx = 1;
		while (1)
		{
			int left = idx * 2;
			int right = idx * 2 + 1;
			if (left > v.size() - 1)
				break;
			else if (left == v.size() - 1 && v[idx]<v[left])	//주의;
			{
				int temp = v[idx];
				v[idx] = v[left];
				v[left] = temp;
				break;
			}
			else
			{
				if (v[left] >= v[right] && v[idx] < v[left])
				{
					int temp = v[idx];
					v[idx] = v[left];
					v[left] = temp;
					idx = left;
				}
				else if (v[right] > v[left] && v[idx] < v[right])
				{
					int temp = v[idx];
					v[idx] = v[right];
					v[right] = temp;
					idx = right;
				}
				else
					break;
			}
		}
	}
	void push(int i)
	{
		v.push_back(i);
		int idx = v.size() - 1;
		while (1)
		{
			if (idx/2 <= 0)
				break;
			if (v[idx] > v[(idx / 2)])
			{
				int temp = v[idx];
				v[idx] = v[(idx/2)];
				v[(idx / 2)] = temp;
				idx /= 2;
			}
			else
				break;
		}
	}
};

int N;

int main()
{
	ios::sync_with_stdio(false);	//이 부분 생략했더니;
	cin.tie(NULL);	//시간초과 나는데;
	cout.tie(NULL);	//왜인지 모르겠다;
	cin >> N;
	int temp = 0;
	heap *h = new heap();	//heap h = heap()으로도 가능;
	for (int i = 0; i < N; i++)
	{
		cin >> temp;
		if (!temp)
		{
			h->max();
			cout << "\n";
		}
		else
		{
			h->push(temp);
		}
	}
	h = 0;
	return 0;
}

11/18-11/25 PS 1/7