안녕하세요 기린입니다 :)
오늘은 힙 정렬(Heap Sort)에 대해 알아보겠습니다. 먼저 힙 정렬은 병합 정렬과 퀵 정렬만큼 정렬속도가 빠른 알고리즘입니다. 그리고 실제 고급 프로그래밍 기법으로 자주 사용하기 때문에 반드시 알고 넘어가야 할 정렬 알고리즘이지요.
힙 정렬은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법입니다. 힙 트리 구조를 이해하기위해 먼저 힙과 트리 구조에 대해 알아야 합니다.
가장 먼저 트리 구조 중 이진 트리(Binary Tree)에 대해서 알고있을 필요가 있습니다. 이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드(Node)에 담은 뒤에 노드를 두 개씩 이어 붙이는 구조를 말합니다. 이 때 트리구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗히는데 이진 트리는 모든 노드의 자식 노드가 2개 이하인 노드로 구성되어 있다 할 수 있죠
흔히 위와 같은 구조를 이진 트리라 하는데요. 여기서 트리(Tree) 라는 것은 말 그대로 가지를 뻗어나가는 것처럼 데이터가 서로 연결되어 뻗어 나간다는 뜻입니다. 트리 구조는 그 형태에 따라서 종류가 굉장히 다양한데 우리가 알아야할 완전 이진 트리(Complite Binary Tree)에 대해 알아보도록 합시다.
완전 이진 트리는 데이터가 루트(Root) 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리입니다. 즉 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 뺵빽히 가득 찬 구조입니다. 예를 들어 데이터가 1부터 7까지 총 7개라면 이것을 트리에 삽입하면 다음과 같은 순서로 들어갑니다. 참고할 부분은 항상 왼쪽 자식 노드부터 데이터가 들어간다는 것입니다.
이해되시나요? 다음은 힙(Heap)에 대해 알아보도록 하겠습니다. 힙은 최솟값이나 최댓값을 최대한 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리입니다. 힙에는 최대 힙과 최소 힙이 존재하는데 최대 힙은 '부모 노드'가 '자식 노드'보다 큰 힙이라고 할 수 있습니다. 일단 힙 정렬을 하기 위해서는 정해진 데이터를 힙 구조를 가지도록 만들어야 합니다.
힙이 어떻게 생겼는지 알기 위해서 힙의 예제들을 살펴봅시다. 최대 힙은 부모 노드의 값이 자식 노드보다 커야 하는데요. 아래 예제를 보시죠
여기서 트리 안의 특정 노드 때문에 최대 힙이 붕괴되는 경우도 있는데요 아래 그림을 보시면, 중간에 있는 데이터 5를 가지는 노드 때문에 최대 힙이 아니지만 그 위쪽은 최대 힙이 형성되어있는걸 확인하실 수 있습니다.
여기서 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용합니다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해서 수행하는 것입니다. 또한 해당 '하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태'라고 가정을 한다는 특징이 있습니다. 위의 그림이 정확히 해당 가정에 부합하는데요, 위 트리에서 5만 최대 힙 정렬을 수행해주면 전체 트리가 최대 힙 구조로 형성되는 상태가 됩니다.
힙 생성 알고리즘은 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘입니다. 또한 위치를 바꾼 뒤 여전히 자식이 존재한다면 또 자식 중에서 더 큰 자식과 자신의 위치를 바꿔주는것이죠. 자식이 더이상 존재하지 않을 때 까지 반복하는것입니다.
힙 생성 알고리즘은 전체 트리를 힙 구조를 자기도록 만든다는 점에서 굉장이 중요한 알고리즘입니다. 이러한 힙 생성 알고르짐의 시간 복잡도는 몇 일까요? 한 번 자식 노드로 내려갈 때마다 노드의 갯수가 2배씩 증가한다는 점에서 O(logN)입니다. 예를 들어 데이터의 갯수가 1024개라면 대략 10번 정도만 수행하면 된다는 거에요.
다음의 데이터를 오름차순으로 정렬하세요.
7 6 5 8 3 5 9 1 6
기본적으로 완전 이진 트리를 푠하는 가장 쉬운 방법은 배열에 그대로 삽입하는 겁니다. 현재 정렬할 데이터가 총 9개이므로 인덱스 0부터 8까지 차례대로 담아주는 것입니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 7 | 6 | 5 | 8 | 3 | 5 | 9 | 1 | 6 |
이진 트리로 바꿔보면
말 그대로 배열에 있는 인덱스가 그대로 차례대로 트리로 표현된 것입니다. 위와 같은 상황에서 모든 원소를 기준으로 힙 생성 알고리즘을 적용하여 전체 트리를 힙 구조로 만들면 되는데요. 이 때 데이터의 갯수가 N개 이므로 전체 트리를 힙 구조로 만드는 복잡도는 O(N * logN)입니다. 참고로 모든 데이터를 기준으로 힙 생성 알고리즘을 쓰지 않아도 되기 때문에 O(N)에 가까운 속도를 낼 수 있습니다.
시간복잡도가 고작 O(N * logN)으로 위와 같이 최대 힙 구조를 만들수 있습니다. 이제부터 정렬을 직관적으로 수행할 수 있는데요. 가장 먼저 루트(Root)에 있는 값을 가장 뒤쪽으로 보내면서 힙 트리의 크기를 1씩 빼주는 겁니다.
위와 같이 9와 6을 바꾼 뒤에 9는 정렬이 완료된 것이므로 초록색으로 처리합니다. 이제 9를 제외하고 나머지 8개 원소를 기준으로 힙 생성 알고리즘(Heapify)를 수행합니다. 결과는 다음과 같습니다.
8과 9가 정렬이 이루어 졌습니다. 이제 이 과정을 반복하시면 되는데요, 힙 생성 알고리즘의 시간 복잡도는 O(log N)이고 전체 데이터의 갯수가 N개이므로 전체 시간 복잡도는 O(N * logN)이라고 할 수 있습니다.
힙 정렬의 전체 시간 복잡도는 O(N * logN)입니다.
자 그럼 마지막으로 소스 코드를 보시겠습니다.
#include <stdio.h>
int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};
int main(void) {
// Change heap structure
for (int i = 0; i < number; i++) {
int c = i;
do {
int root = (c - 1) / 2;
if (heap[root] < heap[c]) {
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
c = root;
} while (c != 0);
}
// Perform repeatedly while reducing the size.
for (int i = number - 1; i >= 0; i--) {
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
int root = 0;
int c = 1;
do {
c = 2 * root + 1;
// Find a lager value among child nodes
if (c < i - 1 && heap[c] < heap[c + 1]) {
c++;
}
// Exchange if the child node value is greater than the root node value
if (c < i && heap[root] < heap[c]) {
int temp = heap[root];
heap[root] = heap[c];
heap[c] = temp;
}
root = c;
} while (c < i);
}
// Ouput
for (int i = 0; i < number; i++) {
printf("%d ", heap[i]);
}
}
힙 정렬은 병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않으므로 메모리 측면에서 효율적입니다. 그리고 항상 시간 복잡도 O(N * logN)을 보장한다는 점에서 강력한 알고리즘이라 할 수 있죠. 이론적으로는 퀵 정렬, 병합 정렬보다 더 우위에 있다고 할 수 있습니다. 하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 더 빠르므로 힙 정렬이 일반적으로 많이 사용되지는 않은걸 참고해주시기 바랍니다 :)
마지막으로 최대 힙을 활용한 오름차순 정렬에서 힙 생성 함수(Heapify)는 특정한 노드를 기준으로 위쪽으로 올라가는 상향식 구현 방식과 아래쪽으로 내려가는 하향식 구현 방식이 있습니다. 두 방식 모두 시간 복잡도는 동일하다는 특징이 있습니다. 참고로 위 본문에서는 상향식 구현 방식으로 진행했으니 하향식 구현 방식도 스스로 고민해보시길 바랍니다.
자 그럼 즐거운 코딩하세요
문의: ralla0405@gmail.com
