Sign In

Access your saved progress

or

Intermediate 25 min

What is Heap Sort?

Heap Sort is an efficient sorting algorithm that uses a binary heap data structure. It builds a max heap, then repeatedly extracts the maximum element to build the sorted array.

The Basic Idea

Heap sort works by:

More elements All sorted Build Max Heap Extract Max Swap to End Heapify Repeat Sorted!

Why Heap Sort is Efficient

Heap sort combines the best features:

  1. Guaranteed O(n log n): Like merge sort
  2. In-place: Only O(1) extra space
  3. No worst case: Always O(n log n)
  4. No recursion: Can be implemented iteratively

Visual Example

Watch heap sort in action:

Heap Sort Visualization

1x
Pseudo Code
1 heapSort(arr):
2 buildMaxHeap(arr)
3 for i = n-1 down to 1
4 swap(arr[0], arr[i])
5 heapify(arr, 0, i)
6
7 heapify(arr, i, n):
8 largest = i
9 l = 2*i + 1, r = 2*i + 2
10 if l < n && arr[l] > arr[largest]
11 largest = l
12 if r < n && arr[r] > arr[largest]
13 largest = r
14 if largest != i
15 swap(arr[i], arr[largest])
16 heapify(arr, largest, n)

Key Characteristics

  • Time complexity: O(n log n) in all cases
  • Space complexity: O(1) - in-place sorting
  • Stable: No - may change relative order
  • Uses heap: Binary max heap data structure

Real-World Use

Heap sort is used when:

  • You need guaranteed O(n log n) performance
  • Memory is limited (in-place)
  • You want to avoid worst-case scenarios
  • Building priority queues

What’s Next?

Now that you know what heap sort is, let’s learn about binary heaps.

Progress 14%
Page 1 of 7
← Previous → Next