[Algorithm] 힙

힙 (Heap)

힙(Heap)은 완전 이진트리인 특별한 트리를 기반으로 한 자료구조이다.

힙에는 최대힙과 최소힙이 있는데, 최대힙은 최대값을 다루는데 특화되어 있고 최소힙은 최소값을 다루는데 특화되어 있다. 각 힙은 일련의 원소들이 주어졌을 때 최대 or 최소 원소를 빠르게 조회, 삭제할 수 있다. 또한 각 힙 모두 임의의 원소를 빠르게 삽입할 수 있다. 최대, 최소 원소를 다루는 특수적인 상황에 있어 효율적이고, 의외로 최대 최소 원소를 활용해야 하는 상황이 많이 발생하기 때문에 굉장히 중요한 자료구조에 속한다. (우선순위큐도 힙으로 제작된다.)

 

힙에서 제공하는 연산들을 배열과 비교해보자. 

 

값 삽입

배열 : O(1)

힙 : O(log N)

 

최대값 or 최소값 삭제

배열 : O(N)

힙 : O(logN)

 

최대값 or 최소값 조회

배열 : O(N)

힙 : O(1)

 

다양한 상황에 대해서 안정적인 속도를 보여준다.

(또한 힙은 완전이진트리를 이용하기 때문에 트리형태의 자료구임에도 불구하고 배열을 이용하여 구현이 가능하고 이는 운영체제의 메모리 참조속도에 있어서도 탁월하다.)

 

힙의 구조

완전이진트리

기본적으로 힙은 완전이진트리에 속한다. 이진트리중에서도 마지막 레벨의 오른쪽부분을 제외하고 모든 노드가 꽉 찬 이진트리를 완전이진트리라 부른다. 다음 그림 중 좌측 트리들은 완전이진트리이고, 우측 트리들은 완전이진트리가 아니다.

 

이러한 특성으로 인해 완전이진트리를 활용하기 전 유용한 전제들을 미리 확보할 수 있다.

1. 완전이진트리는 이진트리의 높이를 H라 할때, 2^H - 1 개의 노드를 갖는다.

2. 완전이진트리에는 빈 공간 없이 원소들이 배치되기 때문에 배열로 표현이 가능하다.

 

다음 그림을 보자. 

 

맨 위에 레벨의 왼쪽에서 오른쪽으로 순서대로 원소를 나열한다면 다음과 같이 배열에 원소를 넣을 수 있을 것이다.

[0]	[1]	[2]	[3]	[4]	[5]
1	12	9	5	6	10

 

완전이진트리의 모든 노드를 꽉 채운다는 특성은 트리의 노드 개수에 대한 정확산 계산이 가능하게 한다. 그러므로 다음과 같이 일반화할 수 있다.

[2^0개]   [2^1개]   [2^2개] ...       [2^(L-1) - K개]
a1        b1, b2    c1, c2, c3, c4    t1, t2 ... tx

 

 

노드의 개수를 정확하게 계산할 수 있기 때문에 각 노드의 배열상 위치도 정확하게 알 수 있다. 이 특성을 활용하면 배열 인덱스 계산으로 트리상의 자식 노드와 부모 노드를 참조하는 것도 가능하다.

(배열의 주소를 0부터 사용하는 경우 아래와 같이 인덱싱이 가능하지만, 주소를 1부터 사용하는 경우 인덱싱이 달라질 수 있다.)

// node index
int index = 1;
int parentIndex = (index - 1) / 2;		// [0] : 1
int lChildIndex = (index + 1) * 2 - 1;		// [3] : 5
int rChildIndex = (index + 1) * 2;		// [4] : 6

 

 

힙의 조건

힙은 이러한 완전이진트리의 속성을 충족하며 동시에 모든 노드에 대해, 자신의 양쪽 자식 노드보다 크거나 같게(혹은 작거나 같게) 트리의 상태를 유지하는 자료구조이다. 이 상태를 유지 시킨다면 필연적으로 힙의 루트는 최대값 혹은 최소값이 된다. 

 

 

의문점들이 있다. 힙은 원소가 같더라도 서로 다른 구조를 갖을 수 있는 것인가? 

그렇다. 위 그림의 힙을 보자. 17 아래에 15, 10이 있는데 두 노드의 위치를 바꾸더라도 힙으로서의 조건을 충족한다. 그러므로 원소의 조합이 같더라도 무수히 많은 구조의 힙이 존재할 수 있다.

(힙의 연산을 그토록 효율적일 수 있었던 건, 이러한 특성이 기반이 되었기 때문이라고 생각한다.)

 

 

힙의 연산

최대힙은 모든 노드들에 대해, 자신의 모든 자식보다 값이 커야 한다. 그러므로 최대힙을 구현하려면 어떠한 상황에도 이 조건을 유지할 수 있도록 해야 할 것이다. 힙이 만들어질 때, 힙에 원소가 삽입될 때, 힙에서 원소가 제거될 때와 같이 모든 상황을 정의하고 각 상황에서 힙이 유지되도록 각 연산들을 정의해보자.

 

힙이 만들어질 때

힙에 원소를 삽입할 때 힙이 유지된다고 가정하자. 각 원소를 넣을 때마다 힙이 유지되기 때문에, 귀납적으로 모든 원소를 넣어도 힙은 유지된다. 그러므로 힙의 삽입이 잘 구현되었다면, 모든 원소에 대해 힙에 원소를 삽입하는 연산을 이용하면 최초로 힙을 만들 수 있다.

 

힙에 원소를 삽입할 때

힙에 원소를 삽입하는 과정은 다음과 같다.

1. 마지막 위치에 삽입할 원소를 넣는다.

2. 부모 노드와 비교하며 적절한 위치를 찾을 때까지 거슬러 올라간다.

최대힙이 다음과 같이 있을 때,
      10
    /    \
   5      3
  / \
 2   4

원소 15가 새로 삽입되면 일단 가장 마지막에 위치시킨다.

      10
    /    \
   5      3
  / \    /
 2   4  15

새로 삽입한 원소는 마지막 위치에서부터 부모 방향으로 힙을 재구성하며 거슬러 올라간다.
1.
      10
    /    \
   5      15
  / \    /
 2   4  3
 
 2.
      15
    /    \
   5      10
  / \    /
 2   4  3

 

이처럼 단순하게 힙을 유지할 수 있는 이유는 새로 삽입된 원소가 이동하는 경로 외 모든 영역에서는 이미 힙이 유지되고 있기 때문이다.

 

 

 

힙에서 원소를 제거할 때

힙에서 원소를 제거하는 과정은 다음과 같다.

1. 루트노드의 값을 제거한다.

2. 맨 마지막 원소를 제거된 루트노드 위치에 대체시킨다.

3. 루트에서 자식으로 힙을 재구성한다. 

 

최대힙이 다음과 같이 있을 때,
      10
    /    \
   5      3
  / \
 2   4
 
최대 원소는 루트 노드인 10 이다.
마지막 원소는 4 이다.
최대 원소를 제거하고, 루트 노드를 4로 대체한다.

      4
    /    \
   5      3
  / 
 2   

루트에서부터 자식으로 힙을 재구성한다. 
재구성 과정은 다음과 같다.
1. 현재 값이 양쪽 자식 모두보다 작으면 두 자식 중 더 큰 자식과 교체한다.
2. 현재 값이 자식보다 작으면 그 자식과 교체한다.
3. 현재 값(4)이 모든 자식보다 값이 크다면 멈춘다.
      5
    /    \
   4      3
  / 
 2

 

 

기타

Heap vs BST

힙과 이진탐색트리에 대해 헷갈려하는 경우가 종종 있다. 둘 다 이진트리 기반의 자료구조이고 이진탐색트리에서 제공해주는 기능들이 힙에서 제공하는 기능들을 포함하고 있기 때문일수도 있다. 

이전에 이진탐색트리에서도 키를 기반으로 최대값과 최소값을 O(logN)에 값 참조, 삽입, 삭제할 수 있는데다가 정렬까지 해주는데 힙을 왜쓰는지에 대한 질문을 받았었다. 이에 대한 대답은 복합적일 수 있다.

차이점을 나열해보면 다음과 같다.

 

1. 이진탐색트리는 원소에 중복이 있어서는 안된다. 반면 힙은 중복을 허용한다.

2. 이진탐색트리는 정렬된 상태를 유지하지만, 힙은 정렬되지 않는다.

3. 이진탐색트리는 정렬된 상태가 보장되기 때문에, 중간 어떠한 값이라도 참조할 수 있지만 힙은 루트에 위치한 값 외에는 참조를 하는 의미가 없다.

4. 이진탐색트리는 O(logN)의 참조, 삽입, 삭제를 지향하지만, 최악의 경우 O(N)까지도 가능하다. 반면, 힙은 어떠한 상황에서도 깔끔한 O(logN)의 삽입 삭제가 보장되며, 삭제를 요구하지 않는 값 참조에 있어서는 O(1)이 보장된다. (레드블랙트리나 AVL 트리는 O(logN)을 보장한다.)

5. 이진탐색트리는 노드 기반으로 구현되지만 힙은 배열 기반으로 구현된다. 이는 캐시메모리 적중률을 늘려주기 때문에 상당한 성능상의 이점을 얻을 수 있다. 

6. 이진탐색트리의 초기 생성은 아무리 빨라도 O(N*logN)이지만, 힙은 O(N)에 가능하다.

 

결론은 최대값, 최소값만 다루는 상황에서는 이진탐색트리보다 힙이 훨씬 유리하다.

 

힙의 구현

 

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
typedef long long ll;

class Heap
{
public:
	Heap(int bucketSize)
		:
		_bucket(bucketSize),
		_heapSize(0)
	{}

	// 힙의 마지막 위치에 새 원소 배치 후 위로 올라가며 힙을 복구한다.
	void Insert(int value)
	{
		int index = _heapSize;
		_bucket[index] = value;
		_heapSize++;

		while (index > 0)
		{
			int parentIndex = (index - 1) / 2;
			int parentValue = _bucket[parentIndex];

			if (parentValue < value)
			{
				std::swap(_bucket[parentIndex], _bucket[index]);
			}

			index = parentIndex;
		}
	}

	// 맨 위 원소를 제거하고, 마지막 원소를 맨 위에 배치 후 아래로 내려가며 힙을 복구한다.
	int Delete()
	{
		assert(_heapSize > 0);

		_heapSize--;
		int ret = _bucket[0];
		_bucket[0] = _bucket[_heapSize];

		int index = 0;

		while (index < _heapSize)
		{
			int lChildIndex = (index + 1) * 2 - 1;
			int rChildIndex = (index + 1) * 2;

			// 양쪽 자식 노드가 모두 현재 노드보다 작으면 현재 위치에 정착한다.
			if ((lChildIndex >= _heapSize || _bucket[lChildIndex] <= _bucket[index]) &&
				(rChildIndex >= _heapSize || _bucket[rChildIndex] <= _bucket[index]))
			{
				break;
			}

			// 양쪽 자식 노드 모두 현재 노드보다 큰 경우, 더 큰 자식과 교체한다.
			if (lChildIndex < _heapSize &&
				rChildIndex < _heapSize &&
				_bucket[lChildIndex] > _bucket[index] &&
				_bucket[rChildIndex] > _bucket[index])
			{
				if (_bucket[lChildIndex] > _bucket[rChildIndex])
				{
					swap(_bucket[index], _bucket[lChildIndex]);
					index = lChildIndex;
				}
				else
				{
					swap(_bucket[index], _bucket[rChildIndex]);
					index = rChildIndex;
				}
			}
			else if (lChildIndex < _heapSize && _bucket[lChildIndex] > _bucket[index])
			{
				swap(_bucket[index], _bucket[lChildIndex]);
				index = lChildIndex;
			}
			else if (rChildIndex < _heapSize && _bucket[rChildIndex] > _bucket[index])
			{
				swap(_bucket[index], _bucket[rChildIndex]);
				index = rChildIndex;
			}
			else
			{
				assert(false);
			}
		}

		return ret;
	}

	int Size() const { return _heapSize; }

	void Print() const
	{
		cout << _heapSize << "   ";
		for (int i = 0; i < _heapSize; ++i)
		{
			cout << _bucket[i] << " ";
		}
		cout << endl;
	}

private:

	vector<int> _bucket;
	int _heapSize;
};


int main()
{

	Heap heap(10);
	heap.Insert(3);
	heap.Print();
	heap.Insert(2);
	heap.Print();
	heap.Insert(1);
	heap.Print();
	heap.Insert(5);
	heap.Print();
	heap.Insert(6);
	heap.Print();
	heap.Insert(4);
	heap.Print();

	while (heap.Size() > 0)
	{
		int value = heap.Delete();
		cout << "pop : " << value << endl;
		heap.Print();
	}

	return 0;
}