힙 정렬 (Heap Sort)

Contents

0. 직접 돌려보기
1. 힙(Heap)
완전 이진 트리
배열로 표현하기
힙 속성
2. 힙 정렬의 흐름
3. sift-down (heapify)
4. 예시: [4, 10, 3, 5, 1]
힙 만들기
최댓값 빼기
5. 복잡도와 특징
다른 O(n log n) 정렬과 비교
6. 정리

힙 정렬은 배열을 힙으로 만든 뒤, 가장 큰 값을 하나씩 끝으로 보내면서 정렬하는 방법. 바로 아래 직접 돌려보기에서 C와 Python 코드를 랜덤 입력으로 실행하고 정렬 과정을 막대로 볼 수 있음

0. 직접 돌려보기

1~5절에서 설명하는 그대로 짠 C와 Python 코드. Run을 누를 때마다 5 ~ 99 사이 랜덤 값으로 새 배열을 만들어서 실행함
C는 Compiler Explorer(godbolt.org)에서 GCC로 컴파일해서 실행하고, Python은 브라우저 안의 Pyodide에서 실행함
프로그램이 비교(CMP), 교환(SWAP), 확정(SORTED)할 때마다 한 줄씩 출력하고, 페이지가 그 출력을 읽어서 막대로 다시 그림. 그래서 화면에 보이는 과정은 실제 실행 결과 그대로
코드를 고쳐서 돌려도 됨. 출력 형식만 지키면 그대로 그려짐

Loading visualizer…

파란색은 비교, 빨간색은 교환, 검은색은 제자리를 찾은 값. 회색은 아직 힙 안에 있는 값
앞부분(Build max-heap)에서는 큰 값이 앞쪽(왼쪽)으로 올라가고, 뒷부분(Move the max to the end)에서는 가장 큰 값이 오른쪽 끝부터 하나씩 검게 쌓임

1. 힙(Heap)

완전 이진 트리

마지막 레벨을 빼고는 노드가 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 이진 트리
빈칸이 없어서 배열 하나로 표현 가능. 포인터가 필요 없음

배열로 표현하기

0번 인덱스부터 쓰면 인덱스 i 노드의 가족은 이렇게 계산됨

관계	인덱스
왼쪽 자식	`2i + 1`
오른쪽 자식	`2i + 2`
부모	`(i - 1) / 2` (정수 나눗셈)

배열   [10, 5, 3, 4, 1]
인덱스   0  1  2  3  4

         10 (0)
        /      \
     5 (1)     3 (2)
    /    \
 4 (3)   1 (4)

크기가 n이면 자식이 있는 노드는 0 ~ n/2 - 1까지. 그 뒤는 전부 잎(leaf)

힙 속성

max-heap: 모든 노드가 자기 자식보다 크거나 같음 → 루트(a[0])가 최댓값
min-heap: 반대로 모든 노드가 자식보다 작거나 같음 → 루트가 최솟값
형제끼리는 순서가 없음. 위 예시에서 5와 3 중 누가 왼쪽이든 상관없음
오름차순 정렬에는 max-heap을 씀. 최댓값을 꺼내서 배열 뒤에서부터 채우기 때문

2. 힙 정렬의 흐름

두 단계로 끝남

힙 만들기 (build): 입력 배열을 그 자리에서 max-heap으로 바꿈
최댓값 빼기 (sort): 루트(최댓값)를 힙의 마지막 칸과 바꾸고, 힙 크기를 1 줄인 뒤 루트를 다시 제자리로 내려보냄. 힙에 하나 남을 때까지 반복

2단계에서 뒤로 보낸 값은 다시 건드리지 않음. 배열 뒤쪽부터 정렬된 구간이 한 칸씩 늘어남
새 배열을 만들지 않고 입력 배열 안에서 자리만 바꿈 → 제자리(in-place) 정렬

3. sift-down (heapify)

힙 정렬의 핵심 연산. 루트 자리에 들어온 값이 힙 속성을 깨뜨렸을 때, 그 값을 아래로 내려보내서 고침

현재 노드와 두 자식 중 가장 큰 값을 찾음
현재 노드가 가장 크면 끝
아니면 더 큰 자식과 자리를 바꾸고, 바뀐 자리에서 1부터 반복

sift_down(a, i, size):          # 힙은 a[0 .. size-1]
    loop:
        largest = i
        left, right = 2i + 1, 2i + 2
        if left  < size and a[left]  > a[largest]: largest = left
        if right < size and a[right] > a[largest]: largest = right
        if largest == i: return
        swap a[i], a[largest]
        i = largest

한 번 내려갈 때마다 트리 한 층씩 내려감 → 최대 트리 높이 log n번
힙 크기 size를 따로 넘기는 이유: 2단계에서 뒤쪽 정렬된 칸을 힙으로 착각하지 않게 하려고

4. 예시: [4, 10, 3, 5, 1]

힙 만들기

자식이 있는 마지막 노드(n/2 - 1 = 1)부터 0까지 거꾸로 sift-down

단계	한 일	배열
시작		`[4, 10, 3, 5, 1]`
`i = 1` (값 10)	자식 5, 1보다 큼 → 그대로	`[4, 10, 3, 5, 1]`
`i = 0` (값 4)	자식 중 10이 더 큼 → 0↔1 교환	`[10, 4, 3, 5, 1]`
내려간 4 (`i = 1`)	자식 5가 더 큼 → 1↔3 교환	`[10, 5, 3, 4, 1]`

결과 [10, 5, 3, 4, 1]이 1절 그림의 max-heap

최댓값 빼기

힙 크기	한 일	배열 (`
5 → 4	10을 끝으로 (0↔4), 1을 내림 (0↔1, 1↔3)	`[5, 4, 3, 1 \| 10]`
4 → 3	5를 끝으로 (0↔3), 1을 내림 (0↔1)	`[4, 1, 3 \| 5, 10]`
3 → 2	4를 끝으로 (0↔2), 3은 자식 1보다 큼 → 그대로	`[3, 1 \| 4, 5, 10]`
2 → 1	3을 끝으로 (0↔1)	`[1 \| 3, 4, 5, 10]`

마지막에 남은 하나는 자동으로 제자리 → [1, 3, 4, 5, 10]

5. 복잡도와 특징

항목	값	이유
힙 만들기	`O(n)`	아래쪽 노드일수록 많지만 내려갈 거리가 짧음. 합치면 `n`에 비례
최댓값 빼기	`O(n log n)`	`n - 1`번 × sift-down 한 번에 최대 `log n`
전체	`O(n log n)`	최선·평균·최악 모두 같음. 입력이 이미 정렬돼 있어도 빨라지지 않음
추가 공간	`O(1)`	입력 배열 안에서 교환만 함
안정성	불안정	멀리 떨어진 칸끼리 바꿔서, 같은 값의 원래 순서가 뒤바뀔 수 있음

다른 O(n log n) 정렬과 비교

정렬	최악	추가 공간	안정성	메모
힙 정렬	`O(n log n)`	`O(1)`	불안정	최악도 보장되고 메모리도 안 씀
병합 정렬	`O(n log n)`	`O(n)`	안정	같은 값의 순서가 중요할 때
퀵 정렬	`O(n²)`	`O(log n)`	불안정	평균적으로 가장 빠름 (캐시 친화적)

힙 정렬은 배열 앞쪽과 뒤쪽을 오가며 접근해서 캐시 효율이 낮음. 실제 속도는 보통 퀵 정렬보다 느림
그래서 단독보다는 최악을 막는 보험으로 자주 쓰임. C++ std::sort의 introsort는 퀵 정렬이 너무 깊어지면 힙 정렬로 바꿈

6. 정리

힙은 완전 이진 트리라서 배열 하나로 표현됨. 자식은 2i + 1, 2i + 2
힙 정렬 = 힙 만들기 O(n) + 최댓값을 끝으로 보내고 sift-down n - 1번
항상 O(n log n), 추가 메모리 O(1), 불안정 정렬