Algorithm Guidecomplexity: O(n log n)

힙 정렬 (Heap Sort)

배열을 Max Heap 구조로 재구성한 뒤 루트(최댓값)를 반복적으로 추출하여 정렬하는 제자리(in-place) 알고리즘입니다. 최악의 경우에도 O(n log n)이 보장됩니다.

01힙 정렬 (Heap Sort)

알고리즘 작동 원리 탐색

힙 정렬을 시작합니다. 늘 가장 큰 값이 꼭대기에 오도록 배열을 최대 힙으로 만든 뒤, 그 값을 하나씩 뒤로 빼냅니다.

1단계 · 힙 만들기. 자식이 있는 마지막 노드부터 거슬러 올라가며 부모가 자식보다 크도록 정리합니다.

80은 자식 40보다 큽니다. 이 자리는 이미 조건을 만족하니 그대로 둡니다.

30은 두 자식 70·10보다 작습니다. 더 큰 자식 70과 자리를 바꿔야 합니다.

70을 위로 올리고 30을 내립니다. 내려간 자리에는 자식이 없어 여기서 멈춥니다.

꼭대기 차례입니다. 50은 두 자식 70·80보다 작으니 더 큰 80과 바꿉니다.

80이 꼭대기로 올라갑니다. 내려간 50은 새 자식 40보다 커서 더 내려갈 필요가 없습니다.

최대 힙이 완성됐습니다. 이제 꼭대기에는 전체에서 가장 큰 80이 있습니다.

2단계 · 빼내기. 꼭대기의 80을 맨 뒷자리와 맞바꿔 확정하고, 그 자리를 힙에서 떼어냅니다.

남은 값으로 다시 정리하면 70이 꼭대기로 올라옵니다. 같은 방법으로 뒤에서 두 번째 자리에 확정합니다.

다시 정리하니 50이 꼭대기입니다. 뒤에서 세 번째 자리에 내려놓습니다.

이번 꼭대기는 40입니다. 그다음 자리에 확정하고 힙을 더 줄입니다.

마지막으로 30을 확정합니다. 힙에는 이제 값 하나만 남습니다.

힙 정렬이 끝났습니다. 꼭대기의 최댓값을 뒤에서부터 채워 넣은 결과가 오름차순입니다.

Live Python

1def heap_sort(arr):

# n: 6

2 n = len(arr)

3 for i in range(n // 2 - 1, -1, -1):

4 heapify(arr, n, i)

5 for i in range(n - 1, 0, -1):

6 arr[0], arr[i] = arr[i], arr[0]

7 heapify(arr, i, 0)

9def heapify(arr, n, i):

10 largest = i

11 l = 2 * i + 1

12 r = 2 * i + 2

13 if l < n and arr[l] > arr[largest]:

14 largest = l

15 if r < n and arr[r] > arr[largest]:

16 largest = r

17 if largest != i:

18 arr[i], arr[largest] = arr[largest], arr[i]

19 heapify(arr, n, largest)

1 / 14

02 쉽게 이해하기

For Everyone

🔑핵심 동작

전체를 힙으로 만든 뒤 꼭대기의 최댓값을 끝으로 빼내기를 반복합니다. 추가 메모리가 거의 필요 없습니다.

💡쉽게 말하면

데이터를 힙으로 만든 뒤 최댓값을 반복해 꺼내 뒤부터 채웁니다.

추가 메모리 없이 O(n log n)을 보장해요.

📍어디에 쓰나

–메모리 제약 정렬
–우선순위 기반 처리

03 파이썬 구현 코드

힙 정렬 (Heap Sort)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)