[C] Heap Sort:: 힙정렬

안녕하세요. 우주신 입니다. 

오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 

힙 정렬(Heap Sort)은 힙(Heap) 성질을 이용하여 정렬(Sort)하는 방식이다. 

힙은 최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 

고안된 완전이진트리(Complete binary tree)를 기본으로 하는 자료구조이다. 

힙은 두 가지가 종류가 있는데, 최대 힙(Max Heaps), 최소 힙(Min Heaps)이다. 

최대 힙은 부모가 자식 노드의 값보다 더 큰 노드 값들로 구성된 트리이다.

밑의 그림은 최대 힙의 예시이다.

[용어 정리]

- 노드, 인덱스 = 주소

- 노드 값 = 주소 안에 있는 값

그리고 트리는 당연히 배열로 표현할 수 있다. 

이 때, 부모 인덱스가 i라면 왼쪽 자식은 2 * i, 오른쪽 자식은 2 * i + 1이 된다. 

**여기서 i가 0 or 1, 어디서 부터 시작하는지 고려해서 코드를 짜야한다.

자, 이제 힙에 대해 알았으니 이를 활용하여 어떻게 정렬하는지 알아보겠다.

힙 정렬을 위해선 크게 두 가지 과정이 필요하다.

 

주어진 데이터를 바탕으로 힙 트리를 구성하고

이 힙 트리를 활용하여 정렬하면 된다.

우리는 여기서 최대 힙을 사용하여 정렬하겠다.

1. 힙 트리 구성 

(1) 주어진 데이터로 구성된 배열을 받아온 후에 중간 지점을 선택한다. 

(2) 중간 인덱스부터 제일 앞 인덱스까지 Heapify 하며 트리를 재구성 한다.

이 부분이 헷갈릴 수 있는데, 정확히 이해하고 넘어가자.

우선, Heapify는 특정 노드를 중심으로 그 밑의 트리들이 힙 성질을 만족하게끔 만드는 작업이다.

밑의 예시를 보면 2번 노드가 Heapify 할 차례라고 하자.

이 때, 2번 노드의 4는 자식 노드 값보다 작으므로 최대 힙 성질을 만족하지 않는다.

힙 성질을 만족하기 위해 밑의 자식 중 더 큰 자식의 4번 노드의 14와 자리를 바꾼다.

그리고 자리가 바뀌었기 때문에 4번 노드를 중심으로 또 Heapify를 한다.

4번 노드의 값 4는 9번 노드의 값 8보다 작기 때문에 최대 힙 성질을 만족하지 못한다. 

4번과 9번 자리를 바꾸면 최종적으로 2번 노드를 중심으로 Heapify가 완성된다. 

중간 노드부터 루트 노드로 Heapify를 하는 이유는 항상 중간 노드부터 자식이 존재하기 때문이다.

예를 들어, 위 그림을 보면 전체 크기가 10인 트리 중에 5번 인덱스 부터 자식이 존재하는 것을 알 수 있다. 

코드를 보자.

먼저, arr 배열과 배열의 사이즈를 인자로 받은 후 배열의 중간 지점을 저장하였다.

int mid = size/2 - 1

여기서 배열의 index가 0부터 시작하는 것을 고려하여 

중간을 (배열 전체 사이즈 / 2 - 1)을 하였다. 

그리고 반복문을 돌며 mid부터 0까지 heapify를 하면 최대 힙이 완성된다.

추상화하여 이해부터 하고 넘어가는 것이 좋을 것 같아서 heapify 코드는 제일 밑에서 설명 했습니다.

2. 정렬

힙 트리를 만들었으면 정렬은 식은 죽 먹기다.

최대 힙의 루트 노드(첫번째 인덱스)는 전체 노드 중 가장 큰 값이므로 이를 활용하면 된다.

(1) 루트 노드의 값을 뽑아 마지막 노드의 값과 바꿉니다. 

(2) 전체 트리의 사이즈를 하나 감소 시킨다. ((1)번에서 뽑은 노드를 가장 큰 수로 마지막 자리에 고정 시켰기 때문에)

(3) 루트 노드를 중심으로 Heapify 하여 힙 트리를 재구성 한다.

그리고 트리의 사이즈가 1이 될 때까지 (1) ~ (3)을 반복하면 정렬이 완성된 것을 알 수 있다.

코드를 보겠습니다.

buildMaxHeap()을 통해 최대 힙을 만들고,

루트 노드, arr[0]을 뽑아 마지막 노드 arr[size-1]와 Swap 한다.

size-- 를 감소 시키며,size가 1이 될 때까지 힙 트리를 heapify 한다.

* Heapify 함수 설명 *

마지막으로 heapify 코드를 보자

힙정렬 중 heapify 코드가 상대적으로 복잡한데, 밑의 코드를 보며 확실히 이해 해보자

여기서 heapify 함수는 인자로, 배열, 배열의 크기, 배열의 중간 인덱스를 받았다.

그리고 그 중간 인덱스를 parent_node에 저장한 후, 왼쪽 자식과 오른쪽 자식의 인덱스도 초기화 한다.

가장 큰 노드를 알아야 하므로 우선은 parent_node를 largest_node로 초기화 한다.

첫번째 if 구문에서 왼쪽 자식 노드가 있는지 확인을 하고 있다면 왼쪽 자식 노드와 부모 노드의 값을 비교한다.

만약에 왼쪽 자식 노드의 값이 부모 노드의 값보다 크다면 largest_node에 부모 노드의 인덱스를 저장한다.

그 후 오른쪽 자식 노드와도 똑같은 방법으로 비교를 한다.

마지막으로 parent_node와 largest_node가 다른지를 확인 하고 다르다면 해당 자식 노드와 Swap을 한다.

만약 Swap이 일어났다면 노드 간의 자리가 바꼈음을 의미하므로 바뀐 노드를 대상으로 재귀적으로 heapify를 한다.

꼭 직접 구현해 보셔서 완벽하게 이해하시길 바랍니다.

Full code는 https://github.com/jjkyun/sorting 참고하시면 됩니다.

고생하셨습니다.

끝

# 참고 # 

 - "Introduction to Algorithm" Cormen, Charles, Ronald, Clifford

- 한양대학교, 정형수 교수님, 알고리즘 수업