Problem Statement❯

You are given an array of integers. Your task is to sort the array using the Heap Sort algorithm. Heap Sort works by converting the array into a max heap and repeatedly removing the maximum element and placing it at the end of the array until it is fully sorted.

Examples❯

Input Output Description
[4, 10, 3, 5, 1] [1, 3, 4, 5, 10] Normal case with a mix of unsorted values. Heap Sort first builds a max heap, then repeatedly extracts the largest value.
[1] [1] Edge case with a single element. Already sorted by definition.
[] [] Empty array. There’s nothing to sort, so the result is also an empty array.
[9, 8, 7, 6, 5] [5, 6, 7, 8, 9] Array in descending order. Heap Sort will reorder it in ascending order by repeatedly extracting the maximum.

Solution❯

Understanding the Problem

We are given an array of numbers and we need to sort them in increasing order. Instead of using built-in sorting, we will implement Heap Sort, which is an efficient comparison-based sorting technique based on a binary heap data structure. Our goal is to understand how heap sort works step-by-step, including edge cases, using a beginner-friendly example.

Example to Understand

Let’s consider the input array: [4, 10, 3, 5, 1]. We want to sort this into: [1, 3, 4, 5, 10].

Step-by-Step Explanation

  • Step 1: Build a Max Heap
    A Max Heap is a binary tree where each parent node is greater than or equal to its children. For the array [4, 10, 3, 5, 1], we reorganize the array to follow the max heap property: [10, 5, 3, 4, 1].
  • Step 2: Swap the Max Element with the Last
    Swap the first element (maximum) with the last element: [1, 5, 3, 4, 10]. Now 10 is in its correct sorted position.
  • Step 3: Heapify the Root
    After removing the largest element (by reducing heap size), we heapify the new root (1) to maintain max heap: [5, 4, 3, 1, 10].
  • Step 4: Repeat the Process
    Continue the swap and heapify until the heap is reduced to one element:
    • Swap 5 and 1 → [1, 4, 3, 5, 10], heapify → [4, 1, 3, 5, 10]
    • Swap 4 and 3 → [3, 1, 4, 5, 10], heapify → [3, 1, 4, 5, 10]
    • Swap 3 and 1 → [1, 3, 4, 5, 10], done.
  • Final Sorted Array: [1, 3, 4, 5, 10]

Handling Edge Cases

Case 1 - Single Element

Input: [1]

  • Only one element is already sorted.
  • No heap to build, return as-is: [1]

Case 2 - Empty Array

Input: []

  • Nothing to sort. Return empty array immediately.

Case 3 - Reverse Sorted Input

Input: [9, 8, 7, 6, 5]

  • It’s already in max order, which helps form the max heap directly: [9, 8, 7, 6, 5].
  • Swap and heapify process will still work as normal.
  • Final sorted output: [5, 6, 7, 8, 9]

Case 4 - All Elements Are Same

Input: [5, 5, 5, 5]

  • Heap sort works fine. Swapping and heapifying won't change positions, but the algorithm still runs.
  • Sorted output is the same: [5, 5, 5, 5]

Algorithm Steps❯

  1. Build a max heap from the input array.
  2. The largest element is now at the root of the heap.
  3. Swap the root with the last element, then reduce the heap size by one.
  4. Heapify the root to maintain the heap property.
  5. Repeat steps 3 and 4 until the heap size is 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n log n)Building the max heap takes O(n) time, and the subsequent n extractions each require O(log n) heapify operations, resulting in O(n log n) even in the best case.
Average CaseO(n log n)Heap sort performs n extract-max operations, and each requires a heapify step that takes O(log n) time. This results in an average-case time complexity of O(n log n).
Worst CaseO(n log n)In the worst case, every extraction causes the largest number of heapify steps (log n), repeated n times. Thus, the overall time complexity is O(n log n).

Space Complexity❯

O(1)

Explanation: Heap sort is performed in-place with no need for additional memory allocation beyond a few variables, resulting in constant auxiliary space usage.

Mallikarjuna Mallisetty, author
About the author

Mallikarjuna Mallisetty

General programming

Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.

View LinkedIn profile ↗