[간단 정리] 힙 정렬

* 오름차순 기준입니다

 

생각보다 쉽지 않았다. 처음에 개념을 잘못 잡는 바람에 완전히 이해하기까지 반나절 정도 걸렸다. 현상을 이해하는 방식이 꽤 자주 스스로도 특이하다고 느껴질 때가 있다. 친절하게 설명하려면 그림을 곁들여야 하는데, 바람은 언제나 텍스트만으로 마무리 짓는 것이다. 그러기 위해서는 두괄식으로 설명해야 할 듯하다.

 

힙은 자료구조로서 '키'의 우선 순위가 있을 때 유용하다. 기본적으로 완전 이진 트리다. 트리의 왼쪽부터 데이터가 삽입되기 때문에 배열을 이용하면 매우 편하다. 순차적으로 인덱스를 활용할 수 있기 때문. 데이터는 키를 통해  최대 힙 혹은 최소 힙으로 정렬한다.

 

최대 힙은 부모 노드가 자식 노드보다 크거나 같고, 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 속성이다. 최대 힙으로 정렬하면 루트에 가장 큰 키가 오게 된다. 여기서 끝이 아니다. 아직은 레벨 단위로 대소만 구분해놓은 상태다. 루트가 가장 큰 숫자, 그다음 레벨이 그다음으로 큰 숫자들, 그다음 레벨은 그다음으로 큰 숫자들. 최대 힙으로 정렬된 데이터는 오름차순으로 정렬할 수 있다. 다음 이미지를 확인하자.

순서 무작위의 데이터

 

최대 힙으로 정렬된 상태

 

부모 노드와 자식 노드 간의 관계만 따지기 때문에 레벨 3의 5번째 인덱스(루트는 0)의 값인 7이 레벨 4의 8번째 인덱스의 값보다 작은 경우도 생길 수도 있다. 이렇게 된 데이터를 어떻게 오름차순으로 정렬할 수 있을까? 힙을 만드는 과정을 heapify라고 표현하는데, 자세한 건 소스를 만나기 전에 설명하기 하고, 최대 힙을 만든 방법을 그대로 활용한다는 사실만 알아두자. 어차피 이론적인 걸 이해해도 소스를 이해하는 건 또 다른 문제다.

 

루트에 가장 큰 값이 있기 때문에 루트의 값과 마지막 노드와 교환(swap)한다. 그러면 다음과 같다.

 

이 상태에서 heapify를 진행하면 아래와 같이 된다. 8은 오른쪽 자식 노드인 12보다 작기 때문에 둘을 교환한다. 그다음 8은 왼쪽 자식 노드의 값인 7과 오른쪽 자식 노드인 10과 값을 비교하는데, 크기가 더 큰 오른쪽 노드 값(10)과 교환한다. 이 과정을 반복하고 나니까 루트에 13 다음으로 큰 12가 위치하게 됐다. 여기에서 주의할 점은, 이 과정이 오름차순을 위한 것이라는 걸 기억하는 것이다. 탐색 대상 중 가장 큰 숫자를 배열의 뒤부터 차례로 정렬하기 때문에 탐색할 때 이미 정렬된 노드는 건드리면 안 된다. 이 과정을 끝까지 반복하면 오름차순으로 데이터가 정렬된다.

 

루트 인덱스는 1이 아니라 0이다. 부모 인덱스(i)를 알고 있을 때 왼쪽 자식 노드의 인덱스는 2 * i + 1, 오른쪽 자식 노드의 인덱스는 2 * i + 2가 된다. 최대 힙으로 데이터를 정렬할 때 마지막 부모 노드(자식 노드 아님)부터 역순으로 루트까지 진행하는데, 역순으로 해야 루트에 가장 큰 데이터를 올릴 수 있기 때문이다. 마지막 부모 노드의 인덱스는 데이터의 사이즈가 n일 때, n / 2 -1이다. 매 인덱스마다 heapify를 진행하면 된다. 재귀 호출을 이용한다.

 

>>구현

##include <cstdlib>
#include <cstdio>

void PrintArray(int arr[], int n);
void Heapify(int arr[], int n, int i);
void HeapSort(int arr[], int n);
void Swap(int& a, int& b);

int main()
{
	int arr[] = { 12, 11, 13, 5, 6, 7, 10, 9, 8 };
	int n = sizeof(arr) / sizeof(arr[0]);

	HeapSort(arr, n);

	printf("Sorted array is\n");
	PrintArray(arr, n);
}

void Heapify(int arr[], int size, int parent)
{
	int largest = parent; // Initialize largest as root 
	int left = 2 * parent + 1;
	int right = 2 * parent + 2;

	// If left child is larger than parent
	if (left < size && arr[left] > arr[largest])
		largest = left;

	// If right child is larger than largest so far 
	if (right < size && arr[right] > arr[largest])
		largest = right;

	// If largest is not parent 
	if (largest != parent)
	{
		Swap(arr[parent], arr[largest]);

		// Recursively Heapify the affected sub-tree 
		Heapify(arr, size, largest);
	}
}

// main function to do heap sort 
void HeapSort(int arr[], int n)
{
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--)
		Heapify(arr, n, i);

	PrintArray(arr, n);

	// One by one extract an element from heap
	for (int i = n - 1; i >= 0; i--)
	{
		// Move current root to end 
		Swap(arr[0], arr[i]);

		// call max Heapify on the reduced heap 
		Heapify(arr, i, 0);
	}
}

void PrintArray(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}