[C++] 최대 힙 (Max Heap) 구현하기 (부제 : Priority Queue)

최대 힙 (Heap) 이란?

최대 힙 (Max Heap) 은 아래 그림과 같이,

부모의 값이 자식의 값보다 항상 큰 자료구조이다.

항상 루트에 최대 값을 가지기 때문에,

이를 이용해서 우선순위 큐 (Priority Queue) 를 구현할 수 있다.

 

최대 힙의 시간 복잡도는

삽입 (Push) 할 때 O (log N),

삭제 (Pop) 할 때 O (log N) 

이므로, 굉장히 합리적인 자료구조임을 알 수 있다.

 

* 참고로 위의 그림에서 루트가 최소가 되는 구조라면 최소 힙 (Min Heap) 이 된다.

 

 

 

동작 원리

최대 힙은 배열을 통해서 구현한다.

위의 최대 힙을 배열로 나타내면 다음과 같다.

 

 

이 그림에서 알 수 있듯이, 배열을 통해서 구현하면

다음의 사실을 이용할 수 있다.

 

- 부모의 인덱스 * 2 = 왼쪽 자식의 인덱스

- (부모의 인덱스 * 2) + 1 = 오른쪽 자식의 인덱스

- 자식의 인덱스 / 2 = 부모의 인덱스 (정수 연산으로, 소수 생략)

 

즉, 2번 노드의 자식은 4번 / 5번 인덱스가 되는 것이다.

이러한 특성을 이용해서 힙의 연산을 빠르게 할 수 있다.

 

 

 

삽입 연산 (Push)

아래처럼, 9 의 값을 가지는 노드를 새로 삽입한다고 생각해보자.

 

 

새롭게 만들어지는 자리를 가정하고,

이 자리에서부터 부모와 지속해서 값을 비교한다. (루트까지 비교될 때까지)

즉, 가장 처음에는 6과 값을 비교할 것이다.

 

 

새롭게 들어온 노드의 값이 크기 때문에,

부모와 자리를 교환한다.

 

 

이번에도 상위 노드 (루트 노드인 7) 와 값을 비교한다.

루트 노드보다 값이 더 크므로,

새로운 노드는 아래 그림처럼 루트 노드가 되었다.

 

삽입 과정은 이런 식으로

가장 아래에서부터, 위쪽 방향으로

새롭게 삽입될 위치를 정해나가는 방식이다.

 

 

 

삭제 연산 (Pop)

 

위와 같은 상태에서 삭제 연산을 수행한다고 생각해보자.

루트 노드인 9 의 값이 삭제되므로 아래와 같은 상태가 된다.

 

 

이제 이 상태에서, 마지막 노드를 루트 노드에 가져다 놓는다.

 

 

그리고 이번에는,

루트 노드로부터 시작해 자식 노드와 비교하면서

루트 노드의 적절한 자리를 찾아나간다. 아래와 같이 말이다.

 

 

이러한 과정을 반복하면,

결과적으로 다시 루트에 최대 값이 들어가있는 최대 힙이 완성된다.

 

 

 

구현 (C++)

#include <iostream>
#include <ctime>

#define HEAP_SIZE	100

using namespace std;

typedef struct {
	int key;
} element;

typedef struct {
	element heap[HEAP_SIZE];
	int heapSize;
} Heap;

void heapPush(Heap* h, element item)
{
	int idx = ++(h->heapSize);

	while ((idx != 1) && (h->heap[idx / 2].key < item.key))
	{
		h->heap[idx] = h->heap[idx / 2];
		idx /= 2;
	}

	h->heap[idx] = item;
}

element heapPop(Heap *h)
{
	element item = h->heap[1];
	element temp = h->heap[(h->heapSize)--];
	int parent = 1;
	int child = 2;

	while (child <= h->heapSize)
	{
		if (child < h->heapSize && h->heap[child].key < h->heap[child + 1].key)
			child++;
		if (temp.key > h->heap[child].key) break;

		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}

	h->heap[parent] = temp;
	return item;
}

element heapPeek(Heap* h) { return h->heap[1]; }
int heapSize(Heap* h) { return h->heapSize; }
bool isHeapEmpty(Heap* h) { return h->heapSize == 0; }
void heapInit(Heap* h) { h->heapSize = 0; }

int main(void)
{
	Heap h;
	heapInit(&h);

	srand(time(NULL));
	for (int i = 0; i < 20; i++)
	{
		element e = { rand() % 10000 + 1 };
		heapPush(&h, e);
	}

	for (int i = 0; i < 20; i++)
		cout << heapPop(&h).key << " ";
	cout << '\n';

	return 0;
}