이번 주제는 Heap Sort 알고리즘입니다.
Heap Sort 를 알기 위해선 Heap 이란 자료구조에 대한 설명이 필요하겠군요.
Heap 은 일반적으로 완전 이진트리(Complete Binary Tree) 로 추상화됩니다.
- 포화 이진트리와 완전 이진트리의 차이점은 알고 계시리라 생각하겠습니다. -
우선 Max - heap 을 봅시다.
각 자식 노드와 부모 노드의 값을 비교할 때, 부모 노드의 값이 자식 노드들 보다 크게끔 완전 이진트리를 구현합니다.
그리고 재귀적으로 모든 서브 트리에 대해 위와 같은 정의를 적용해 주고, 그 이후 이 완전 이진트리를 level 별로 순회해 가면서
배열에 넣어주면 Max - heap 이 완성됩니다.
- 즉, 각 서브 트리 별 루트 노드의 값이 서브 트리의 레코드 중에서 가장 큰 레코드 값이 되도록 만들어 주면 됩니다. -
Min - heap은 가장 작은 레코드값이 루트에 있는 것이구요.
이제 Heap Sort 를 해 볼까요.
Max - heap 의 정의에서 Max - heap은 그 서브 트리 중 루트 노드가 가장 큰 레코드 값을 가진다고 되어 있습니다.
Heap Sort 를 위해선 필요한 작업이 두 가지 있습니다.
- Max -heap 을 이용한 오름차순 정렬의 경우는 루트 노드의 값을 역순으로 배열합니다. -
2. 루트 노드를 빼고 나서도 Heap(Max - heap 이든 Min - heap 이든) 의 특성을 무너뜨리지 않는 것.
저 중 두 번째. Heap 의 특성을 무너뜨리지 않는 것이 가장 중요합니다.
저것 때문에 코드가 꽤 복잡하게 나오는 경향이 있죠 -_-;
흠... 아마 호기심 많은 분들이라면 이런 말을 하실 수도 있겠습니다.
" 왜 배열을 이용하나요? 트리 구조의 구현은 링크드 리스트를 이용하던데. "
네. 좋은 질문입니다. ㅇ_ㅇ
일반적으로 트리 구조를 구현해 보면 Unbalanced tree 가 나오는 경우 - 그것도 심하게 -, 배열로 구현하게 되면
인덱스의 낭비가 너무 심하죠.
따라서 보통 Linked List 를 이용해서 구현하도록 학교, 또는 학원에서 가르칠 겁니다.
하지만 Heap 의 경우는 그럴 걱정이 없습니다.
아까 Heap 의 추상화 과정에서 말씀드렸을 겁니다. '완전 이진트리' 를 사용한다구요.
아시다시피 완전 이진트리는 균형잡힌 Balanced tree 입니다. 따라서 인덱스의 낭비를 걱정할 이유가 없죠.
그러므로, 골치아프게 Linked List를 이용하지 않고도 충분히 배열로 구현할 수가 있는겁니다.
자... 그러면 알고리즘을 정리해 봅시다.
n 개 레코드의 오름차순 정렬 알고리즘입니다.
- 일반적으로 Max - heap 을 생성한다.-
2. Heap 을 무너뜨리자.
- Heap 의 루트 노드를 빼서 기존 배열 - Heap - 의 가장 마지막 인덱스(n - 1)에 삽입한다. -
3. 빠진 루트 노드를 채워넣으면서 Heap 의 특성을 유지한다.
4. 다시 Heap 을 무너뜨린다.
- 빼낸 루트 노드를 뒤에서부터 역순으로 넣는다. (n - k) 인덱스 -
5. 4 -> 3 으로 알고리즘을 계속 수행한다.
6. 만약 (n - k) 가 0 이라면 -> 정렬 종료.
- Heap 이 완전히 소멸되었으므로. -
또 다른 질문이 있을 수 있겠습니다.
"어라? 왜 기존 배열에다가 빼낸 노드값을 넣어두나요? 충돌 생기지 않습니까?"
네. 결론적으로 말씀드리면...'안생깁니다.'
Heap을 구현한 배열의 경우, 인덱스 갯수는 n 개입니다.
하지만 Heap Sort 를 하기 위해서 필요한 과정이 있죠. 바로 'Heap 을 소멸시켜라.' 입니다.
따라서 루트 노드의 값을 빼 가면서 Heap을 무너뜨려 가는 것이죠.
저 과정에서 만약 Heap 의 루트 노드를 빼면, Heap 을 이루는 노드들의 갯수는 (n-1) 개 입니다.
따라서 Heap 의 최 말단 노드 바로 뒤에다가 빼낸 루트 노드 값을 넣어줘도 충돌이 생기지 않습니다.
딱 배열의 인덱스 갯수는 n 개를 만족하죠.
이해가 가시나요?
즉, 다시 설명드리자면 Heap 배열을 미리 빼낸 루트 노드값들이 뒤에서부터 점령해 들어 가는 겁니다.
그리고 루트 노드값들로 모든 Heap 배열 이 채워지면 이젠 Heap 이 완전히 소멸되면서 기존의 배열은 정렬된 배열이 되는 거죠.
그럼.. 다음은 코드 구현 차례. 입니다만 -_-;
기존 계획서에서 언급드렸다 시피 생략하겠습니다.
Quick Sort 처럼 구현을 원하시는 분이 계시다면 구현해 드리도록 하죠.