이전에 살펴본 Quick Sort는 Pivot을 기준으로 분할(Partition)하면서 정렬을 진행하는 방식이었습니다. 평균은 O(N log N)이지만, Pivot 선택이 나쁘면 최악 O(N2)까지 떨어질 수 있다는 점이 특징이었죠.
Heap Sort는 같은 O(N log N) 계열이지만, 접근 방식이 완전히 다릅니다. 분할이 아니라, 힙(Heap) 구조로 “최댓값(또는 최솟값)을 반복적으로 꺼내는 방식”으로 정렬을 완성합니다. 그리고 Quick Sort와 달리, 입력 데이터 형태와 무관하게 항상 O(N log N)을 보장합니다.
1. Heap Sort 개요 및 핵심 아이디어
Heap Sort(힙 정렬)는 Binary Heap(이진 힙)을 이용하는 비교 기반 정렬입니다. 핵심은 다음 한 문장으로 요약할 수 있습니다.
"배열을 힙으로 만들고, 루트(최댓값/최솟값)를 끝으로 보내는 작업을 반복한다."
- Max Heap을 만들면 → 매번 최댓값을 꺼내 뒤쪽에 확정 (오름차순 정렬에 일반적)
- Min Heap을 만들면 → 매번 최솟값을 꺼내 뒤쪽에 확정 (내림차순 정렬에 일반적)
- 이 글에서는 일반적인 오름차순 정렬을 목표로 Max Heap을 사용합니다.
Heap Sort는 추가 배열을 만들지 않고(in-place) 배열 내부에서 swap만 수행합니다. 그리고 Quick Sort처럼 Pivot 선택에 따라 최악(O(N2))로 악화되는 경우가 없고, 항상 O(N log N)이 유지되는 것이 가장 큰 장점입니다.
2. Heap이란? (정렬 관점에서 필요한 만큼만)
Heap Sort에서 사용하는 힙은 보통 완전 이진 트리(Complete Binary Tree) 형태의 Binary Heap을 의미합니다. 정렬 관점에서 중요한 규칙은 딱 하나입니다.
- Max Heap: 모든 부모 노드는 자식 노드보다 크거나 같습니다. (루트가 항상 최댓값)
그리고 Heap Sort는 이 힙을 배열로 구현합니다. (포인터 트리 구조를 만들지 않습니다)
※ 배열에서 힙 인덱스 규칙 (0-based)
parent = (i - 1) / 2
left child = i * 2 + 1
right child = i * 2 + 2
Heap Sort는 이 규칙만으로 “부모-자식 관계”를 계산합니다.
※ Heap 구조를 더 자세히 보고 싶다면
Heap Sort에서 사용하는 이진 힙(Binary Heap)의 핵심 개념은 별도의 Heap 문서로 따로 정리하지 않았습니다. 대신, Unity에서 자주 쓰이는 PriorityQueue를 구현하며 Heap의 구조와 동작을 코드 중심으로 설명했으니, Heap을 더 깊이 이해하고 싶다면 아래 글을 참고하시면 좋습니다.
Unity 개발자를 위한 C# PriorityQueue(우선순위 큐) 구현
3. Heap Sort의 전체 흐름
1) Build Max Heap (힙 구성)
- 배열 전체를 Max Heap 형태로 만듭니다.
- 이 단계가 끝나면 array[0]에는 항상 “현재 구간의 최댓값”이 위치합니다.
2) Extract Max 반복 (정렬 확정)
- 루트(최댓값)
array[0]를 배열 맨 뒤로 swap합니다. - 정렬 완료 구간이 뒤쪽에 1칸 늘어납니다.
- 루트가 바뀌었으니 다시 힙 성질을 복구합니다(SiftDown/Heapify).
즉, Heap Sort는 “최댓값을 하나 확정 → 힙 복구 → 최댓값 확정 → 힙 복구 …”를 반복해서 정렬을 완성합니다.
4. 예제로 Heap Sort 과정을 따라가기
예제 배열
[4, 10, 3, 5, 1]
오름차순 정렬을 목표로 하므로 Max Heap을 사용합니다. 즉, 힙의 루트에는 항상 현재 구간의 최댓값이 위치하게 됩니다.
4.1 Build Max Heap (힙 구성)
Build Heap은 마지막 부모 노드부터 0번 인덱스까지 내려가며 SiftDown(Heapify-Down)을 수행합니다.
※ “마지막 부모 노드”란 무엇인가?
배열 기반 힙에서 부모 노드란 자식 노드를 하나라도 가지고 있는 노드를 의미합니다.
(자식 인덱스 규칙: left = 2*i+1, right = 2*i+2)
1) 배열이 10개일 때
index: 0 1 2 3 4 5 6 7 8 9
value: a b c d e f g h i j
부모 노드의 조건은 다음과 같습니다. (왼쪽 자식이 배열 범위 안에 있으면(parent))
2*i + 1 < n
n = 10일 때,
2*i + 1 < 10
2*i < 9
i < 4.5
따라서 부모 노드 인덱스 범위는 0, 1, 2, 3, 4이며, 마지막 부모 노드는 (n/2)-1 = 4가 됩니다.
2) 트리 구조로 보면
(0)
/ \
(1) (2)
/ \ / \
(3) (4) 5 6
/ \ /
7 8 9
주의: 그림의 숫자는 모두 인덱스이며, ()는 “부모 노드(자식이 있는 노드)”를 강조 표시하기 위해 붙였습니다.
이때,
- 부모 노드: 0, 1, 2, 3, 4
- leaf 노드: 5, 6, 7, 8, 9
leaf 노드는 자식이 없으므로 이미 힙 조건을 만족합니다. 따라서 Build Heap에서는 자식이 있는 마지막 노드(4)부터 0번까지 SiftDown을 수행합니다.
즉,
i = 4 → 3 → 2 → 1 → 0
이 순서가 바로 “마지막 부모 노드부터 0번 인덱스까지 SiftDown”의 정확한 의미입니다.
마지막 부모 인덱스
n = 5
마지막 부모 인덱스 = (n / 2) - 1 = 1
SiftDown 순서: i = 1 → 0
※ Heap Sort는 배열 기반 알고리즘이며, 아래 트리 그림들은 내부 구조 이해를 돕기 위한 개념적 표현입니다.
초기 상태
array = [4, 10, 3, 5, 1]
트리(값(인덱스)):
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
(1) i = 1 에서 SiftDown
- i = 1은 배열의 인덱스를 의미하며, 이 위치의 값은 10입니다.
root = 10(1)
left = 5(3), right = 1(4)
10 >= 5 → Max Heap 조건 만족
→ swap 없음
[결과] - 변화 없음
array = [4, 10, 3, 5, 1]
트리:
4(0)
/ \
10(1) 3(2)
/ \
5(3) 1(4)
(2) i = 0 에서 SiftDown
1) root = 4(0), 큰 자식 = 10(1)
swap(0,1)
[결과]
array = [(10), (4), 3, 5, 1]
트리:
10(0)
/ \
4(1) 3(2)
/ \
5(3) 1(4)
2) 계속: root = 4(1), 큰 자식 = 5(3)
swap(1,3)
[결과]
array = [10, (5), 3, (4), 1]
트리 (Build Heap 완료):
10(0)
/ \
5(1) 3(2)
/ \
4(3) 1(4)
Build Heap이 끝난 시점에서 루트에는 최댓값 10이 위치합니다.
4.2 Extract 반복 (정렬 확정 단계)
이제부터는 루트(최댓값)를 배열의 뒤쪽(end)으로 보내며 정렬을 확정합니다. 각 단계마다 최댓값 하나가 확정됩니다.
(1) end = 4
swap(0,4) → 10 확정
array = [1, 5, 3, 4, (10)]
힙 구간(0..3):
1(0)
/ \
5(1) 3(2)
/
4(3)
// SiftDown ---------------------
1 < 5 → swap(0,1)
[결과]
array = [(5), (1), 3, 4, 10]
5(0)
/ \
1(1) 3(2)
/
4(3)
1 < 4 → swap(1,3)
[결과]
array = [5, (4), 3, (1), 10]
트리(복구 완료):
5(0)
/ \
4(1) 3(2)
/
1(3)
(2) end = 3
swap(0,3) → 5 확정
array = [1, 4, 3, (5), 10]
힙 구간(0..2):
1(0)
/ \
4(1) 3(2)
// SiftDown ---------------------
1 < 4 → swap(0,1)
[결과]
array = [(4), (1), 3, 5, 10]
트리:
4(0)
/ \
1(1) 3(2)
(3) end = 2
swap(0,2) → 4 확정
array = [3, 1, (4), 5, 10]
힙 구간(0..1):
3(0)
/
1(1)
3 >= 1 → SiftDown 종료
(4) end = 1
swap(0,1) → 3 확정
array = [1, (3), 4, 5, 10]
정렬 완료
4.3 전체 정렬 결과
[1, 3, 4, 5, 10]
이 예제에서 확인할 수 있듯이, Heap Sort는
- (1) Build Heap으로 루트 = 최댓값 상태를 만들고
- (2) Extract + SiftDown으로 최댓값을 하나씩 확정해 나가며 전체 정렬을 완성합니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Heap Sort(Heapify → Extract 반복)의 흐름을 시각화해 줍니다. “루트가 항상 최댓값”이라는 힙 성질이 어떻게 정렬로 이어지는지 확인하시면 이해가 빨라집니다.
https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
5. 왜 항상 O(N log N)이 보장되는가
Heap Sort의 가장 큰 특징은 평균과 최악의 시간 복잡도가 모두 O(N log N)으로 동일하다는 점입니다. 이는 입력 데이터가 이미 정렬되어 있거나, 특정 패턴을 가지더라도 성능이 급격히 나빠지지 않음을 의미합니다.
1) Build Heap 단계: O(N)
Build Heap은 모든 노드를 동일한 비용으로 처리하는 과정이 아닙니다. 아래쪽 노드일수록 이동할 수 있는 높이가 작고, 위쪽 노드만 상대적으로 더 많은 비교를 수행하기 때문에 전체 비용을 합치면 O(N)으로 수렴합니다.
2) Extract + SiftDown 반복: O(N log N)
- 최댓값 추출(Extract): N번
- 각 추출 후 힙 복구(SiftDown): 트리 높이에 비례하여 O(log N)
따라서 Heap Sort의 전체 시간 복잡도는 O(N) + N · O(log N) = O(N log N)이 됩니다.
6. 공간 복잡도와 특징
- 추가 배열 메모리: 없음 (in-place)
- 공간 복잡도: O(1) (정렬 자체는 배열 내부 swap만 사용)
- 안정 정렬 아님(Stable X): 동일 값의 상대 순서가 유지되지 않을 수 있음
- 항상 O(N log N) 보장: 입력 데이터가 정렬되어 있든 아니든 동일
즉, Heap Sort는 “성능 보장형 O(N log N) + 메모리 효율”이 강점이고, 대신 안정성은 포기하는 정렬입니다.
7. C# 기반 Heap Sort 구현
using System;
namespace Daebak.Common.Algorithms.Sorting
{
/// <summary>
/// Heap Sort (힙 정렬)
/// - Binary Heap(Max Heap) 기반 정렬
/// - 평균/최악 시간 복잡도: O(N log N) (항상 보장)
/// - Build Heap: O(N)
/// - In-place 정렬 (추가 배열 없음)
/// - 안정 정렬 아님 (Stable X)
/// </summary>
public static class HeapSort
{
/// <summary>
/// 외부에서 호출되는 진입점
/// - 전체 배열을 대상으로 Heap Sort 수행 (오름차순)
/// </summary>
public static void Sort(int[] array)
{
if (array == null || array.Length <= 1)
{
return;
}
int n = array.Length;
// 1) Build Max Heap
BuildMaxHeap(array, n);
// 2) Extract Max 반복
// end를 줄여가며, 최대값을 뒤로 확정
for (int end = n - 1; end > 0; end--)
{
// 루트(최댓값)와 end swap → 최댓값 확정
Swap(array, 0, end);
// heap 구간 [0 .. end-1]에 대해 힙 성질 복구
SiftDown(array, 0, end);
}
}
/// <summary>
/// 배열 전체를 Max Heap으로 구성
/// - 마지막 부모 노드부터 0까지 내려가며 SiftDown 수행
/// </summary>
private static void BuildMaxHeap(int[] array, int heapSize)
{
int lastParent = (heapSize / 2) - 1;
for (int i = lastParent; i >= 0; i--)
{
SiftDown(array, i, heapSize);
}
}
/// <summary>
/// SiftDown(Heapify-Down)
/// - startIndex에서 시작해서 아래로 내려가며 Max Heap 조건을 복구
/// - heapSize는 힙으로 취급할 구간의 길이 (0..heapSize-1)
/// </summary>
private static void SiftDown(int[] array, int startIndex, int heapSize)
{
int root = startIndex;
while (true)
{
int left = root * 2 + 1;
int right = root * 2 + 2;
// 자식이 없으면 종료
if (left >= heapSize)
{
break;
}
// 더 큰 자식을 선택 (Max Heap)
int largerChild = left;
if (right < heapSize && array[right] > array[left])
{
largerChild = right;
}
// 루트가 더 크거나 같으면 힙 조건 만족 → 종료
if (array[root] >= array[largerChild])
{
break;
}
// 루트가 작으면 더 큰 자식과 swap 후 계속 내려감
Swap(array, root, largerChild);
root = largerChild;
}
}
/// <summary>
/// 배열 내 두 인덱스의 값을 교환
/// </summary>
private static void Swap(int[] array, int a, int b)
{
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
}8. Unity 환경에서 테스트
using UnityEngine;
using Daebak.Common.Algorithms.Sorting;
public class Test_HeapSort : MonoBehaviour
{
private void Start()
{
int[] data = { 38, 27, 43, 3, 9, 82, 10 };
Debug.Log("Before Sort : " + string.Join(", ", data));
HeapSort.Sort(data);
Debug.Log("After Sort : " + string.Join(", ", data));
}
}
출력 결과
Before Sort : 38, 27, 43, 3, 9, 82, 10
After Sort : 3, 9, 10, 27, 38, 43, 829. 마무리
Heap Sort는 힙의 “루트=최댓값” 성질을 이용해, 최댓값을 하나씩 확정해 나가는 정렬입니다. Quick Sort처럼 평균이 좋은 정렬과 달리, Heap Sort는 입력 형태와 무관하게 항상 O(N log N)을 보장하며, 추가 메모리 없이(in-place) 동작한다는 점이 강점입니다.
※ Quick Sort vs Heap Sort (정리)
• Quick Sort: 평균 O(N log N), 최악 O(N2) 가능 / in-place / 보통 실전에서 매우 빠름
• Heap Sort: 평균/최악 모두 O(N log N) 보장 / in-place / 안정 정렬 아님
“평균 성능”을 끝까지 밀어붙이면 Quick Sort, “최악 보장”이 필요하면 Heap Sort가 강점입니다.
이로써 O(N log N) 계열의 대표 정렬들(병합/분할/힙 기반)의 구조적 차이를 모두 정리했습니다.
※ 다음 글에서는 비교 기반 정렬을 잠깐 벗어나, 입력 값의 범위를 활용하는 Counting Sort(또는 Radix Sort)처럼 “조건이 맞으면 선형 시간”까지 내려가는 정렬을 정리해 보겠습니다. (비교 기반 정렬과 무엇이 다른지, 언제 쓰면 좋은지 중심으로 이어갑니다)
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Radix Sort(LSD) 구현 (0) | 2026.01.21 |
|---|---|
| Unity 개발자를 위한 C# Counting Sort(계수 정렬) 구현 (0) | 2026.01.20 |
| Unity 개발자를 위한 C# Quick Sort(퀵 정렬) 구현 (0) | 2026.01.18 |
| 대박 게임 개발 연구소(Daebak Game Dev Lab) 소개 (0) | 2026.01.15 |
| Unity 개발자를 위한 C# Merge Sort(병합 정렬) 구현 (0) | 2026.01.15 |
