What is the Heap Sort in DSA ?? with free Explanation

Overview

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by building a max-heap (or min-heap) from the input data and then repeatedly extracting the maximum (or minimum) element from the heap and rebuilding the heap until all elements are sorted.

Key Characteristics

Time Complexity: O(n log n) for all cases (worst, average, and best).
Space Complexity: O(1) (in-place sorting).
Stability: Not stable (the relative order of equal elements might change).
Algorithm Type: Comparison-based, in-place sorting.

How Heap Sort Works

Build a Max-Heap: Convert the input array into a max-heap.
Extract the Maximum Element: Swap the root (maximum element) with the last element of the heap, reduce the heap size by one, and heapify the root.
Repeat: Repeat the process until the heap is empty.

Steps and Example

Consider the following unsorted array:

[4, 10, 3, 5, 1]

Step 1: Build a Max-Heap

Convert the array [4, 10, 3, 5, 1] into a max-heap.

Step 2: Extract the Maximum Element

Swap the root (10) with the last element (1), resulting in [1, 5, 3, 4, 10].
Reduce the heap size by one and heapify the root.

Step 3: Repeat

Swap the root (5) with the last element of the reduced heap (1), resulting in [1, 4, 3, 5, 10].
Heapify the root.

      4
     / \
    1   3

Continue this process until the heap is empty, resulting in a sorted array [1, 3, 4, 5, 10].

Visualization

Let’s generate a step-by-step visualization of Heap Sort using diagrams.

Initial Array

[4, 10, 3, 5, 1]

Step 1: Build Max-Heap

Step 2: Extract Maximum and Heapify

Swap 10 and 1:
[1, 5, 3, 4, 10]

Heapify:
      5
     / \
    4   3
   /
  1

Repeat Until Sorted

Swap 5 and 1:
[1, 4, 3, 5, 10]

Heapify:
      4
     / \
    1   3

Swap 4 and 1:
[1, 3, 4, 5, 10]

Heapify:
      3
     /
    1

Swap 3 and 1:
[1, 3, 4, 5, 10]