본 게시글은 정렬 알고리즘 중 힙 정렬에 대한 이해를 증진하기 위한 글로,
요즘 IT의 기술 아티클(링크)을 참고했습니다.
자료 구조는 데이터를 효율적으로 저장, 검색, 삭제할 수 있도록 설계된 구조나 방법을 의미합니다.
이 중, 힙(heap)은 정렬, 우선순위 큐, 스케줄링 같은 다양한 알고리즘에서 활용되는 자료 구조입니다.
1. 힙의 정의
힙은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조를 말합니다.
※ 완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨에 노드가 완전히 채워져 있는 트리 구조를 의미합니다.
힙의 기본 용어는 다음과 같습니다.
- 부모 노드, 자식 노드 : 특정 노드의 상위에 위치한 노드를 모두 부모 노드라고 하며, 특정 노드의 하위에 위치한 노드를 자식 노드라고 합니다.
- 루트 노드, 리프 노드 : 트리 구조에서 가장 상위에 위치한 노드를 루트 노드라고 하며, 가장 밑에 위치하면서 자식 노드가 없는 노드를 리프 노드라고 합니다.
- 레벨, 높이 : 레벨은 루트 노드부터 시작하여 트리의 몇 번째 층에 있는지를 나타냅니다. 보통 루트 노드의 레벨은 0으로 표시합니다. 레벨과 달리 트리의 높이는 리프 노드부터 시작하며, 루트 노드의 높이는 트리의 전체 높이가 됩니다.
2. 힙의 종류
힙의 종류에는 최대 힙(Max-Heap)과 최소 힙(Min-Haep)이 있습니다.
최대 힙은 모든 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 특성을 가집니다. 이러한 특성 때문에 루트 노드는 전체 힙 중에서 가장 큰 값을 가집니다.
반대로, 최소 힙은 모든 부모 노드가 자식 노드보다 작거나 같습니다. 그리고 트리의 루트 노드는 전체 힙 중에서 가장 작은 값을 가집니다.
힙은 보통 배열(Array)을 이용해서 구현합니다. 아래는 자바 코드를 이용한 힙 구현 예시입니다.
public class MinHeap {
public int[] heap;
public int size;
// Min 힙 구축
public void build_min_heap(int[] arr) {
this.size = arr.length;
this.heap = new int[size+1]; // heap[0]은 사용하지 않기 때문
System.arraycopy(arr, 0, heap, 1, size); // heap[1]가 root
for(int i = size/2; i >= 1; i--) {
min_heapify(i);
}
}
// 힙 구조로 재배열
public void min_heapify(int i) {
int left = 2 * i;
int right = 2 * i + 1;
int smallest;
// 왼쪽 자식 노드와 비교
if (left <= size && heap[left] < heap[i]) {
smallest = left;
} else {
smallest = i;
}
// 위에서 비교한 값과 오른쪽 자식 노드와 비교
if (right <= size && heap[right] < heap[smallest]) {
smallest = right;
}
// 자식 노드가 더 작으면 위치를 바꾸고, min_heapify 재귀 호출
if (smallest != i) {
swap(i, smallest);
min_heapify(smallest); // 재귀 호출
}
}
}
heapify() 메서드는 힙의 조건에 맞게 노드의 위치를 재배열하는 역할을 수행합니다.
여기서는 최소 힙이므로 부모 노드가 자식 노드보다 큰 경우 위치를 바꿉니다. 그리고 이 과정을 재귀적으로 진행하여 전체 힙이 최소 힙의 조건을 만족하도록 합니다.
...
// 두 요소의 위치를 바꿈
public void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public void printHeapArray() {
for (int i = 1; i <= size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
...
3. 힙의 시간 복잡도 분석
힙을 재배열할 때 사용하는 heapify() 연산은 O(log n)의 시간 복잡도를 가집니다. 그 이유는 heapify()가 힙의 높이만큼 재귀 호출을 수행하기 때문입니다.
예를 들어, 자식 노드가 최대 2개인 힙에서 전체 노드의 개수가 n이고, h가 힙의 높이라면 n이 4일 때 h는 2가 되고, n이 8일 때 h는 3이 됩니다. 즉, 이를 계산 식으로 표현하면 높이 h = log2n이 됩니다. 따라서 heapify()의 시간 복잡도는 O(log n)이 됩니다.
힙을 구축하는 build_heap()은 일반적으로 O(n)의 시간 복잡도를 가집니다. 아울러 힙의 삽입과 삭제 연산을 할 경우에는 노드의 삽입 또는 삭제 후 트리를 재정렬하기 때문에, 힙의 높이에 따른 O(log n) 시간 복잡도를 갖게 됩니다.
전체 힙의 최대값 또는 최소값을 구하는 경우, 단순히 힙의 루트 값을 조회하면 되기 때문에 O(1)의 시간 복잡도를 갖습니다.
4. 힙을 이용한 정렬 알고리즘
힙 정렬은 힙을 이용하여 배열을 정렬하는 알고리즘입니다. 힙 정렬에서는 정렬되지 않은 배열을 최대 힙이나 최소 힙으로 구성하고, 루트 노드를 가장 마지막 노드와 교환한 후 힙 크기를 줄이는 방식으로 정렬을 수행합니다.
public class HeapSort {
public void heapSort(int[] inputArray) {
MinHeap minHeap = new MinHeap();
// 힙 생성
minHeap.build_min_heap(inputArray);
// 힙 정렬
int j = 0;
for (int i = minHeap.size; i >= 2; i--) {
inputArray[j] = minHeap.heap[1]; // 힙의 root(최소값)을 배열에 저장
j++;
minHeap.swap(1, i); // 힙의 root와 마지막 요소를 바꿈
minHeap.size--; // 힙의 크기를 줄임
minHeap.min_heapify(1); // 힙을 재배열
}
// 힙의 마지막 root 값을 배열 마지막에 저장
inputArray[j] = minHeap.heap[1];
}
}
힙 생성은 일반적으로 O(n)의 시간 복잡도를 가집니다. 그리고 힙 정렬에서는 힙에서 가장 큰(또는 작은) 원소를 제거하고, 힙을 재정렬하는 과정을 n번 반복합니다. 각 제거 연산은 O(log n)의 시간 복잡도를 갖기 때문에 이 과정에서 시간복잡도는 O(n log n)이 됩니다. 따라서 힙 생성을 포함한 힙 정렬의 전체 시간 복잡도는 빅오 표기법에 따라 O(n log n)입니다.
※ 다른 정렬 알고리즘과의 비교
| 구분 | 삽입 정렬 | 병합 정렬 | 퀵 정렬 | 힙 정렬 |
| 최악의 경우 | O(n^2) | O(n log n) | O(n^2) | O(n log n) |
| 평균 경우 | O(n^2) | O(n log n) | O(n log n) | O(n log n) |
| 최선의 경우 | O(n) | O(n log n) | O(n log n) | O(n log n) |
힙 정렬은 퀵 정렬과 같이 별도의 메모리를 사용하지 않는 제자리 정렬(in-place sorting) 방식을 사용합니다. 따라서 힙 정렬은 일정한 성능을 보임과 동시에 별도의 메모리를 사용하지 않는다는 장점이 있습니다.
또한 각 원소가 k 위치만큼 떨어져 있는 배열인 k-sort 배열을 정렬할 때 가장 효율적인 방법으로 사용되기도 합니다. 다만 숫자가 같은 경우에도 스왑이 일어날 수 있기 때문에, 퀵 정렬과 함께 안정적이지 않은 정렬 방식으로 분류됩니다.
참고 출처
- 자료구조 개념 이해하기 '힙과 힙 정렬 알고리즘' (링크)
'알고리즘' 카테고리의 다른 글
| [자바] Collections, Comparator, Comparable 정렬에 대하여 (1) | 2023.12.20 |
|---|---|
| [알고리즘] 병합 정렬과 퀵 정렬 (0) | 2023.10.26 |
