[Baekjoon] 1927번: 최소 힙

 

 

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

1927번: 최소 힙

 

---

 

문제 해결 과정

착안

힙 트리(heap tree) 자료 구조는 최대 또는 최소를 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리(complete binary tree) 형태의 자료 구조이다. 최소 힙의 특성에 따라 문제에서 요구하는 동작을 구현하여 문제를 해결하고자 하였다.

 

이전 포스트에서 유사한 내용(최대 힙)을 다루었기 때문에 이번 포스트에서는 구체적인 내용은 생략하였다.

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

class MinHeap
{
public:
	void Insert(int n)
	{
		int current = Count;
		Data[Count++] = n;

		while (current > 0)
		{
			int parent = (current - 2 + current % 2) / 2;
			if (Data[parent] <= n)
				break;

			Swap(parent, current);
			current = parent;
		}
	}

	int Extract()
	{
		if (!Count)
			return 0;

		int retVal = Data[0];
		Count--;
		Swap(0, Count);

		int current = 0;
		while (current < Count)
		{
			int leftChild = 2 * current + 1;
			if (leftChild >= Count)
				break;

			if (leftChild < Count)
			{
				int minChild = leftChild;
				if (leftChild + 1 < Count)
					if (Data[leftChild] > Data[leftChild + 1])
						minChild++;

				if (Data[current] <= Data[minChild])
					break;
				
				Swap(minChild, current);
				current = minChild;
			}
		}

		return retVal;
	}

private:
	void Swap(int idx1, int idx2)
	{
		int temp = Data[idx1];
		Data[idx1] = Data[idx2];
		Data[idx2] = temp;
	}

private:
	int Data[100000] = { 0, };
	int Count = 0;
};

int N;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N;
	MinHeap heap;
	while (N--)
	{
		int num;
		cin >> num;

		if (num)
			heap.Insert(num);
		else
			cout << heap.Extract() << "\n";
	}

	return 0;
}

 

실행 결과