[Heap] 힙 개념 및 구현(수도코드)

Heap의 개념

힙은 트리의 일종인데, "complete tree"이거나 "nearly complete tree"이어야 한다. 그리고 다음 두 가지 종류로 나뉜다.

max-heap의 경우 각 노드의 key 값이 자식 노드들의 key 값보다 크거나 같고, min-heap의 경우 각 노드의 key 값은 자식 노드들의 key 값보다 작거나 같아야 한다.

Heap의 특성

max-heap을 기준으로 살펴보자. 힙의 root는 트리에서 가장 큰 값을 갖고 있으며, root의 왼쪽/오른쪽 서브트리도 같은 특성을 유지한다. 만약 min-heap이라면 힙의 root가 트리에서 가장 작은 값을 갖게 된다.

구현은 주로 linked list보다는 array로 이루어진다.

노드와 자식 간의 관계는 다음과 같이 확인할 수 있다.

index가 i인 노드를 생각해본다면,

1. • i번째 노드 왼쪽 자식: 2i+1
   • i번째 노드 오른쪽 자식: 2i+2
   • i번째 노드의 부모 노드: floor((i-2)/2)
   • j번째 노드가 왼쪽 자식이면, 오른쪽 자식은 j+1

Heap의 연산

Heap에서 자료를 추가하거나 삭제할 수 있으며, 순회, 검색, 출력과 같은 기능도 작동하게 할 수 있다.

다만 힙은 위에서 언급한, root의 key 값이 가장 크거나 (max-heap) 작아야 (min-heap) 하고 그 특성이 모든 서브트리에 대해서도 동일하게 유지되어야 하며, 정의했던 것처럼 (nearly) complete tree라는 특성도 유지해야 한다.

만약 노드를 추가하거나 삭제를 한 후 그냥 가만히 둔다면 힙의 정의를 만족하지 못할 것이다.

따라서 우리는 Reheap up / Reheap down 이라는 함수를 정의해서 heap의 모양을 유지하도록 한다.

수도코드의 경우, 순회, 검색, 출력 자체는 기존 트리에서 구현하는 것과 동일하므로 건너뛰고, 삽입 및 삭제의 경우는 각각 함수의 뒷부분에서 Reheap up, Reheap down함수를 불러오기만 하면 되므로 건너뛰도록 하겠다. 여기에서는 Reheap Up 및 Reheap Down에 대해서만 소개하도록 하겠다.

Reheap Up

삽입 연산을 수행하면서 같이 불러와야 하는 함수로 가장 마지막에 삽입된 요소를 위쪽으로 이동시키면서 올바른 위치에 갈 수 있게 한다. 삽입 자체는 가장 첫 번째 빈 leaf node에 들어가기 때문에 heap의 구조를 유지하기 위해서는 node를 이동시켜주어야 한다.

삽입된 노드의 부모 노드와 key 값을 비교하여, 만약 삽입된 노드가 부모 노드의 key 값보다 크면 서로 위치를 교환한다. 이 과정을 계속 반복하여 heap의 구조를 유지시킨다.

수도코드는 다음과 같다.

void reheapUp (HEAP *heap, NODE *newNode) {
	if (newNode != root) {
		parent = parent->newNode;
		if (newNode->key > parent->key) {
			swap(newNode, parent);
			reheapUp(heap,parent);
		}
	}
}

Reheap Down

heap은 nearly complete tree이므로 root을 바로 삭제하게 되면, heap의 구조가 유지되지 못한다. 따라서 last tree node의 값을 root로 옮긴 후, root를 아래로 이동시켜서 heap의 배열 특성(heap-ordering property)이 충족되도록 위치를 변경해야한다.

root 노드를 삭제할 때, 그냥 삭제하게 되면 heap의 구조가 붕괴되므로, 자식 노드 중 오른쪽 노드와 값을 교환해가며 heap 구조의 마지막 노드로 이동시킨 후 삭제한다.

수도코드는 다음과 같다.

void reheapDown (HEAP *heap, NODE *root, int last) {
	if (root->left) {
		int leftKey = root->left->key;
		if (root->right) {
			int rightKey = root->right->key;
		}
		else {
			int rightKey = NULL;
		}
	}
	if (leftKey > rightKey) {
		largeSubtree = root->left;
	}
	else {
		largeSubtree = root->right;
	}
	if (root->key < largeSubtree->key) {
		swap(root, largeSubtree);
		reheapDown(heap, largeSubtree, last);
	}
}