Algorithm Guidecomplexity: O(n log n)

힙 정렬 (Heap Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Heap Sort

힙 정렬을 시작합니다. 배열을 Max Heap으로 재구성(Heapify)한 뒤, 루트(최댓값)를 하나씩 추출합니다.

Logic Node1 / 14

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)

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)