[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
- 한양대학교, 정형수 교수님, 알고리즘 수업