[알고리즘&자료구조] 힙 구조 & 힙 정렬

 정렬알고리즘에는 다양한 종류가 있지만, 힙정렬 알고리즘은 힙구조라는 매우 유용한 자료구조를 이용하고있다. 힙구조는 힙정렬뿐만 아니라, 우선순위큐를 구현하는데에도 응용된다. 힙정렬을 구현하기 위해서는 먼저, 힙구조를 이해할 필요가 있다. 힙구조에는 최대힙과 최소힙이 있는데, 최대힙을 구현하는것으로 최소힙은 생략하겠다.
 먼저, 최대힙에 대해서 알아보자. 최대힙이란 기본적으로 2진트리의 모양새를 취한다. 부모노드가 항상 자식노드보다 큰 값을 가지는 구조를 만족한다면 최대힙이다. 따라서 최대힙의 최상위루트의 값이 트리전체의 요소중 최대값임을 알 수있다.

 최대힙을 이용하여 힙정렬을 수행하는 기본원리는 다음과 같다.
 1. 먼저 최대힙을 구성한다.
 2. 최대힙의 최상위루트값(최대값)을 수열의 맨뒤로 보내고 수열의 길이를 하나 줄인다.
 3. 과정2로 인해 수열이 변경되었으므로, 변경된 수열에 대해서 다시 최대힙을 구성한다.
 4. 과정1 ~ 과정3 을 수열의 길이가 1이 될 때 까지 반복한다.
최대힙은 그 이름에서도 알 수 있듯이 최상위루트값이 수열의 최대값이므로 최대값을 계속 추출해내는 작업을 통해서 수열을 정렬하는 것이다.
( 최대힙이 2진트리의 모양새를 하고있다는것은 어디까지나 가상이고, 실제로는 배열에서 모든 처리를 수행하게된다. 즉, 실제 트리구조에서처럼 포인터를 갖는 데이터구조를 만들 필요는 없다.)

 힙정렬을 구현하기에 앞서, 최대힙을 구성해야하는데 최대힙은 기본적으로 2진트리의 모양을 하고 있으므로 2진트리의 기본적인 성질을 알아보자.
2진트리는 자식노드를 단 2개(왼쪽자식과 오른쪽자식)만을가지는 트리구조이다. 배열에서의 인덱스 k 번째요소를 k노드라고 하자. 노드k의 왼쪽자식은 노드(2*k+1) 이고, 오른쪽자식은 노드(2*k+2) 이다. (오른자식을 노드 3k 라고하는것은 적절하지 않다.)  또, 부모노드는 (int)(k*0.5)-1이다. 임의의 노드k 를 기준으로 왼쪽자식노드, 오른쪽자식노드, 부모노드의 인덱스가 모두 계산가능함을 알 수 있다. 지금까지 논의된 구체적인 노드의 인덱스값은 배열의 인덱스값이 0부터 시작되는 환경을 기준으로 했다. 예를들면 C, C++, JAVA 와 같은 언어는 배열이 인덱스0부터 시작된다. 마지막으로, 배열의 요소수가 n개인경우 자식을 적어도 하나이상 가지는 노드는 [0, ( int )( n * 0.5 ) - 1)]이고, 자식을 가지지 않는 리프노드는 나머지 범위가 된다.

 이제, 위의 성질들을 바탕으로하여 최대힙을 구성하는 방법을 생각해 보자.
 전체트리는 부분트리로 구성된다고 생각할 때, 부분트리가 모두 최대힙특성을 가지게 하면 전체트리는 자연스럽게 최대힙특성을 가지게 된다. 자식을 가지지 않는 리프노드는 그 자체로 최대힙특성(상위루트가 자식노드보다 큰 값을 가지는 특성)을 가진다. 따라서, 자식을 하나이상 가지는 노드들에 대해서 최대힙특성을 가지게끔하는 조작을 수행하도록 한다. 이 때, 자식노드와 상위노드의 값이 교환됨에 의해 자식노드를 상위노드로 하는 트리가 최대힙특성을 위반하게될 가능성이 생기므로 변경한 자식노드에 대해 재귀적적으로 최대힙특성을 유지하도록 하여야한다.
 노드k 를 최상위 루트로하는 트리에대하여 최대힙특성을 가지도록 하는 함수는 아래와같다.


void Heapify(int Array[], int k, int HeapSize) { int largest = k; int left = k*2 + 1; int right = k*2 + 2; if(left < HeapSize && Array[left] > Array[k]) largest = left; if(right < HeapSize && Array[right] > Array[largest]) largest = right; if(largest != k){ swap(&Array, k, largest); Heapify(Array, largest, HeapSize); } }

 위의 Heapify 함수에서 HeapSize 는 현재 고려중인 수열의 길이를 의미하며, 힙정렬을 수행할때 필요한 인수값이므로 지금은 넘어가도 좋다. 노드k와 노드k의 왼자식, 오른자식중 가장 큰 값의 인덱스를 찾아서 상위노드값과 교환한다. 그리고 교환에의해 최대힙특성이 위반될 가능성이 생겼으므로, 변경된 노드에 대해서 재귀적으로 Heapify 함수를 호출하고있다.

 다음은 위의 Heapify 함수를 이용하여 주어진 수열을 최대힙으로 만드는 BuildHeap 함수를 살펴보자.
 
void BuildHeap(int Array[], int ArraySize) { int HeapSize = ArraySize; int i = (int)(HeapSize * 0.5) - 1; for(; i>=0; --i){ Heapify(Array, i, HeapSize); } }

  BuildHeap 함수는 적어도 하나이상의 자식을 가지는 노드에 대해서 Heapify 함수를 호출하여 최대힙특성을 만족시키도록 하고있다. 자식을 가지는 노드의 호출순서가 중요한다. 자식을 가지는 노드중에서도 가장 아래쪽 노드부터 트리의 윗쪽 노드의 방향으로 호출하여야 함에 주의하자.

그럼,  최대힙구조를 이용하여 힙소트를 수행해보자. 최대힙구조를 이용하여 힙소트를 수행하는 방법에 대해서는 이 글의 서두에서 한 번 언급이 되었지만 아래에서 다시 한 번 더 확인하자.
 최대힙을 이용하여 힙정렬을 수행하는 기본원리는 다음과 같다.
 1. 먼저 최대힙을 구성한다.
 2. 최대힙의 최상위루트값(최대값)을 수열의 맨뒤로 보내고 수열의 길이를 하나 줄인다.
 3. 과정2로 인해 수열이 변경되었으므로, 변경된 수열에 대해서 다시 최대힙을 구성한다.
 4. 과정1 ~ 과정3 을 수열의 길이가 1이 될 때 까지 반복한다.

 힙소트의 소스코드는 아래와같다.

void HeapSort(int Array[], int ArraySize) { int i = 0; int HeapSize = ArraySize; BuildHeap(Array, ArraySize); for(i=ArraySize-1; i>0; --i){ swap(&Array, 0, i); --HeapSize; Heapify(Array, 0, HeapSize); } }

 HeapSize 는 수열의 길이로 초기화한다음, 최대힙구조에서 최상위루트값을 추출함에 따라서 하나씩 그 값이 줄어들게 하고있다.

 힙소트가 비록 O(n*log(n)) 의 비용으로 정렬이 가능한 매력적인 알고리즘이지만, 일반적으로 Quick Sort 알고리즘이 보다 빠른것으로 알려져있다. 하지만, 힙소트에 이용되는 힙구조는 우선순위큐에의 응용 등 알아두면 유용한 자료구조이므로 소개하였다.