Algorithm Guidecomplexity: O(n log n)

Heap Sort

An in-place algorithm that rebuilds the array into a max-heap and repeatedly extracts the root (maximum) to sort. Guarantees O(n log n) even in the worst case.

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

Repeatedly take the top off a pile that always keeps the maximum on top.

💡In Plain Words

Builds a heap, then repeatedly pops the max and fills from the back.

Guarantees O(n log n) with no extra memory.

📍Where It's Used

–Memory-constrained sorting
–priority-based processing

03 Python Implementation

A clean, readable reference implementation of the core logic of 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)

04 Frequently Asked Questions

FAQ

What is Heap Sort?+

An in-place algorithm that rebuilds the array into a max-heap and repeatedly extracts the root (maximum) to sort. Guarantees O(n log n) even in the worst case.

What is the time complexity of Heap Sort?+

The time complexity of Heap Sort is O(n log n). Follow the step-by-step visualization to see exactly why.

Where is Heap Sort used?+

Memory-constrained sorting, priority-based processing.

What's a simple analogy for Heap Sort?+

Repeatedly take the top off a pile that always keeps the maximum on top.

→ Sorting — see allRelated