Back to course

Lesson 35: Heap Sort Algorithm

Algorithms: From Zero to Hero (A Beginner's Guide)

35. Heap Sort Algorithm

Heap Sort is an efficient, comparison-based sorting algorithm that leverages the Max Heap data structure.

Heap Sort Steps

Heap Sort has two main phases:

  1. Building the Max Heap: Convert the input array into a Max Heap structure. This process takes O(N) time.
  2. Sorting Phase: Repeatedly extract the maximum element (the root) and place it at the end of the array. After extraction, the remaining elements are re-heapified.
    • Swap the root (largest element) with the last element of the heap.
    • Reduce the size of the heap by one.
    • Fix the heap property on the new, smaller heap (a process called heapify), which takes O(log N).

Efficiency

  • Time Complexity: O(N log N) for all cases (Worst, Average, Best). This is because the construction takes O(N), and the N extractions/heapify steps take N * O(log N).
  • Space Complexity: O(1) auxiliary space, making it an in-place sorting algorithm.