Algorithm Guidecomplexity: O(n log n)

힙 정렬 (Heap Sort)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

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 파이썬 구현 코드

힙 정렬 (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)

Guide Progress0%