2-(0) (i)Heap

2-(0)에서는 이후 알고리즘들에 적용될 자료구조들에 대한 기본 내용을 다룰 생각이다. 그냥 자료구조를 좀 빼놓는 것이 좋을 것 같아 이렇게 둔다.

 

해당 단원은 시간 분석을 제외하고는 다른 부분들을 윤성우 저자의 열혈 자료구조에서 가져왔다. 다른 곳에도 설명이 잘 나와있지만 PQ(Priority Queue)와 Heap에 관한 설명이 잘 나와있었기 때문이다. 물론 열혈은 C로 되어있어서 코드는 내가 C++로 작성했다.

 

PQ는 원소들이 우선 순위를 가진 채 Queue에 들어가는 자료구조를 얘기한다. Queue에 자료를 넣을 떄 우선 순위를 고려하여 위치를 정한다고 생각하면 될 것이다. 이런 Queue는 그냥 구현하면 삽입의 위치를 찾기 위해 worst case에 n-time 비교를 해야할 수도 있다.(앞부터 뒤까지 다 보는 경우) 이런 경우는 자료구조의 의미가 없다. 따라서 Priority Queue를 구현할 때 Heap을 사용하여 구현한다고 한다.

 

그렇다면 Heap이라는 자료구조는 어떤 자료구조인가? complete binary tree의 정의를 응용하여 정의해보자. complete binary tree의 간단한 정의는 다음과 같다.

"노드가 위에서 아래로, 왼쪽에서 오른쪽 순서대로 채워져있는 트리"

Heap에는 Max Heap과 Min Heap이 있는데 데이터의 크기에 따른 우선순위 지정의 차이 문제일 뿐이다.

Max Heap은 complete binary tree이면서 모든 노드에 저장된 값이 자식 노드의 값보다 더 크거나 같은 자료구조를 말한다. Min Heap은 저장된 값이 작거나 같은으로 바꾸기만 하면 된다.

 

그러면 Max Heap은 어떻게 만들 수 있는가? 이 BuildHeap연산을 위해 정의하는 Heapify함수가 있는데 그것부터 알아보자. Heapify연산은 다음과 같은 연산이다.(Down을 기준으로 작성하였다. HeapifyUp연산도 모든 논리를 거꾸로하면 root노드의 첫번째 자식부터 BuildHeap하는 방식으로 가능하다.)

<그림1: Heapify란?>

<그림1>에서 볼 수 있듯이 어떤 root노드를 기준으로 왼쪽과 오른쪽에 Heap이 있을 때 root노드를 포함한 전체 tree를 Heap으로 만들어 주는 연산이다. 이는 recursive하게 작동하는 함수인데 그 작동은 다음과 같다.

<그림2: MaxHeapify의 recursive한 definition>

그럼 이제 이 연산을 가지고 다음<그림3> 과 같은 complete tree를 Heap으로 만드는 과정을 생각해보자.

<그림3: Heap(처음에는 그냥 complete tree)과 대응되는 배열>

여기서 leaf노드인 4 5 6 7 8번 노드를 생각해보면, 그 노드들은 아래에 아무것도 없기 때문에 자체적으로 Heap의 정의를 만족한다. 따라서 45678번 노드는 힙이다.

그럼 이제 leaf node들을 child로 갖고 있는 internal node인 3번 노드를 생각해보자 3번 노드를 기준으로 7번과 8번 노드는 힙이다. 따라서 3번 노드를 루트노드로 생각하고 Heapfiy하면 3,7,8번 노드가 힙을 만들게 된다.

2번 노드도 마찬가지로 해보면 된다.(자식이 전부 leaf)

1번 노드를 생각해보면 왼쪽 3번 노드는 아까 그 밑까지 전부 힙으로 만들었고 4번은 leaf node였으므로 Heap, 따라서 Heapify하면 0번 노드의 왼쪽은 전부 힙이 된다. 

0번 노드도 마찬가지 논리로 양 옆이 Heap이니까 0번 노드를 root노드로 생각해서 heapfiy하면 heap이 된다. 따라서 전체적으로 처음의 tree가 heap이 되었다. BuildHeap은 이런 논리로 작동하는데, 가장 마지막의 internal node부터 root노드까지 쭉 Heapify해주기만 하면 된다. 그러면 Heap이 완성된다.

 

상당히 번거로워 보이지만 Time complexity 계산을 해보면 의외로 그 시간이 짧다는 결과가 나온다. 다음은 Heapify의 복잡도 계산 결과인데, root노드를 포함한 Heap에서 Heapify의 재귀적 동작을 식으로 풀어서 계산한 것이다.

<그림4: Time complexity of Heapify>

이것을 코드로 구현해보면 다음과 같다. (가독을 위해 3개의 수를 비교하는 부분을 조금 비효율적으로 짰다.)

void maxHeapify(int* arr,int size,int idx) {
	//역할은 그 노드와 left child, right child 를 비교하여 가장 큰 것을 위에 올리는 것.
	//idx is start point of Heapify
	int leftChild;
	int rightChild;
		//1-(i) Child가 없거나 하나인 경우
	if (2 * idx + 1 > size - 1) //leaf node인 경우
		return;
	else if (2 * idx + 1 == size - 1) //right child만 없는 경우(==leftChild가 배열의 마지막 원소인 경우)
	{
		leftChild = arr[2 * idx + 1];
		rightChild = -INFINITE;
	}
	else {
	//1 - (ii)Child가 다 있는 경우
		leftChild = arr[2 * idx + 1];
		rightChild = arr[2*idx+2];
	}


	//2-(i) parent node is biggest among 3 elements
	if (arr[idx] >= leftChild && arr[idx] >= rightChild)
		return; //Heapify를 밑의 원소들에 대해 할 이유가 없음
	else {//2 - (ii)parent node is smaller than child node
		if (leftChild >= arr[idx] && leftChild >= rightChild){ 
			//leftChild is biggest among 3 elements
			swapPos(arr[idx], arr[2 * idx + 1]);
			maxHeapify(arr, size, 2 * idx + 1);
		}
		else {
			//rigtChild is biggest among 3 elements
			swapPos(arr[idx], arr[2 * idx + 2]);
			maxHeapify(arr, size, 2 * idx + 2);
		}
	}

}

 

 

그러면 build Heap의 time complexity계산은 어떻게 수행할 수 있을까? BuildHeap은 모든 internal node에 대해 수행하는 것으로 생각하면 된다. 대강의 근사를 위해 leaf node의 level에 모든 node들이 꽉 차있는 perfect tree를 생각해보자 그 때 다음 <그림5>와 같은 계산을 해볼 수 있다.

<그림5: BuildHeap의 Time complexity의 증명>

따라서 Build Heap의 시간 복잡도는 O(n)이다. 이것을 코드로 구현해보면 다음과 같다.

void BuildHeap(int* arr, int size) {
	//(i) last index of array is size-1
	//if size-1 = 2n+2(even), last internal node is n, thus n = (size-3)/2
	//if size-1 = 2n+1(odd), last internal node is n, thus n = (size-2)/2
	int lastInternal = (size-1)/2;
	//now Build Heap
	for (int i = lastInternal; i >= 0; i--) {
		maxHeapify(arr, size, i);
	}
}

 

이제 이것을 이용해 HeapSort()하는 방법은 다음 챕터에서 알아본다.