[Baekjoon] 11279번: 최대 힙

 

 

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

11279번: 최대 힙

 

---

 

문제 해결 과정

착안

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

 

완전 이진 트리 형태의 자료 구조 특성상, 배열 형태로 구현하면 부모와 자식 노드를 나타내는 인덱스 사이에 다음과 같은 규칙성이 있어 비교적 편리하게 구현이 가능하므로 배열을 활용하여 구현하고자 하였다.

 

부모 노드를 나타내는 요소의 인덱스를 $p$, 왼쪽 자식 노드와 오른쪽 자식 노드를 나타내는 인덱스를 각각 $c_1, \space c_2$라고 하면, 루트 노드를 0으로 시작하여 완전 이진 트리에서 노드가 추가되는 순서대로 노드들의 인덱스를 부여하면

 

$$c_1 = 2p + 1$$

$$c_2 = 2p + 2$$

 

가 항상 성립한다. 따라서 현재 힙 트리 내의 요소의 개수가 $n$개일 때, 자식 노드를 나타내는 인덱스의 값이 $(n-1)$보다 작거나 같으면 해당 자식 노드가 존재하며 반대의 경우는 자식 노드가 존재하지 않는 경우이다.

 

구현

힙 자료 구조를 구현함에 있어, 완전 이진 트리를 만족하면서 데이터의 입출력 과정 상에서 부모 노드와 자식 노드 사이의 대소관계가 항상 힙 자료 구조를 만족하도록 하는 것이 핵심이므로 이 부분에 중점을 두어 구현하였다. 이 과정에서 부모, 자식 노드를 나타내는 인덱스 사이의 규칙성과 자식 노드의 존재 여부를 판단할 수 있는 연산을 활용하였다.

 

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

#include <iostream>

using namespace std;

class MaxHeap
{
public:
	void Insert(int num)
	{
		int child = Count;
		Data[Count++] = num;

		while (child > 0)
		{
			int parent = (child - 2 + child % 2) / 2;

			if (Data[parent] < num)
				Swap(parent, child);
			else
				break;

			child = parent;
		}
	}

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

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

		int parent = 0;
		while (true)
		{
			int leftChild = 2 * parent + 1;
			int maxChild;

			if (leftChild + 1 > Count)
				break;
			
			if (leftChild + 1 < Count)
				maxChild = Data[leftChild] > Data[leftChild + 1] ? leftChild : leftChild + 1;
			else
				maxChild = leftChild;

			if (Data[parent] < Data[maxChild])
			{
				Swap(parent, maxChild);
				parent = maxChild;
			}
			else
				break;
		}

		return retVal;
	}

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

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

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

	int N;
	cin >> N;

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

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

	return 0;
}

 

실행 결과