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.

01Heap Sort

Explore How It Works

Starting heap sort. Turn the array into a max heap so the largest value always sits on top, then pull that value off to the back one at a time.

Phase 1 · build the heap. Walk up from the last node that has children, making every parent larger than its children.

80 is larger than its child 40. This spot already satisfies the condition, so leave it.

30 is smaller than both children, 70 and 10. It has to trade places with the larger child, 70.

70 moves up and 30 moves down. The slot it lands in has no children, so we stop here.

Now the top. 50 is smaller than both children, 70 and 80, so it swaps with the larger one, 80.

80 rises to the top. The 50 that came down is larger than its new child 40, so it sinks no further.

The max heap is built. The top now holds 80, the largest value of all.

Phase 2 · extraction. Swap the top 80 with the last slot to lock it in, then drop that slot from the heap.

Rebuilding with what remains lifts 70 to the top. Lock it into the second-to-last slot the same way.

Rebuilding again puts 50 on top. Set it down in the third slot from the end.

This time the top is 40. Lock it into the next slot and shrink the heap further.

Finally lock in 30. Only one value is left in the heap.

Heap sort is done. Filling the array from the back with each maximum leaves it in ascending order.

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

For Everyone

🔑How It Works

Builds a heap over the whole array, then repeatedly moves the maximum from the top to the end. Needs almost no extra memory.

💡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?+

Builds a heap over the whole array, then repeatedly moves the maximum from the top to the end. Needs almost no extra memory.

→ Sorting — see allRelated