[알고리즘] 힙 정렬 (Heap Sort)

[알고리즘] 힙 정렬 (Heap Sort)

---

힙정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 따라서 힙(Heap)에 대해서 알아봐야하는데 또 힙을 알기 위해서는 선행적으로 이진 트리(Binary Tree)를 알고 있는 것이 좋다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말한다. 즉, 이진트리는 모든 노드의 자식이 2개 이하인 노드를 가지고 있는 구조이다. 

이진 트리

그리고 데이터 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근 차근 들어가는 구조의 이진트리를 완전 이진 트리 고한다.

완전 이진 트리

힙(Heap)은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 힙에는 최대힙과 최소힙이 존재하는데 최대힙은 부모 노드가 자식 노드보다 큰 힙이며, 일단 힙정렬을 하기 위해서는 정해진 데이터를 힙의 구조로 만들어야한다. 

최대 힙 구조

힙(Heap)을 이용해 데이터를 정렬 해보자!!!

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자!

7, 10, 5, 8, 1, 6, 3, 4, 2, 9

소스코드 구현 (C++)

#include <iostream>

using namespace std;

int main()
{
	int temp;
	int arr[10] = { 7, 10, 5, 8, 1, 6, 3, 4, 2, 9 };
	// 힙구조로 바꾼다
	for (int i = 1; i < 10; i++)
	{
		int c = i;
		do 
		{
			int root = (c - 1) / 2;
			if (arr[root] < arr[c])
			{
				temp = arr[root];
				arr[root] = arr[c];
				arr[c] = temp;
			}
			c = root;
		} while (c != 0);
	}

	//힙 생성 알고리즘 후
	cout << "Heapify = [";
	for (int i = 0; i < 10; i++)
	{
		if(i != 9) cout << arr[i] << ", ";
		else cout << arr[i];
	}
	cout << "]" << endl;

	//크기를 줄여가며 반복적으로 힙을 구성, 오름차순으로 변경
	for (int i = 10 - 1; i >= 0; i--)
	{
		temp = arr[0];
		arr[0] = arr[i];
		arr[i] = temp;
		int root = 0;
		int c = 1;
		do 
		{
			c = 2 * root + 1;
			//자식 중 더 큰값 찾기
			if (arr[c] < arr[c + 1] && c < i - 1)
			{
				c++;
			}
			//루트보다 자식이 더 크다면 스왑
			if (arr[root] < arr[c] && c < i)
			{
				temp = arr[root];
				arr[root] = arr[c];
				arr[c] = temp;
			}
			root = c;
		} while (c < i);
	}
	
	//힙 정렬
	cout << "Heap Sort = [";
	for (int i = 0; i < 10; i++)
	{
		if (i != 9) cout << arr[i] << ", ";
		else cout << arr[i];
	}
	cout << "]" << endl;
	return 0;
}

출력 결과

시간 복잡도 계산

최대 힙의 구조를 만들기 위해서는 힙 생성 알고리즘(Heapify Algorithm)이 사용되며 이것은 트리의 높이와 같기때문에 시간복잡도는 1/2N * log2N 가 소요 된다. 즉 이것을 시간복잡도로 간편하게 표기하면 O(N * logN)이된다.

---

힙 정렬은 병합 정렬과는 다르게 추가적 컨테이너가 필요하지 않기에 메모리 측면에서는 효율적이고 항상 O(N * logN)의 시간복잡도를 보장한다. 하지만 단순히 속도를 가지고 비교하면 특정 상황을 제외하고 퀵정렬이 더 빠르기 때문에 많이 사용되지는 않는다고 한다.