Heap Sort Algorithm

What is Heap Sort?

Heap Sort is a fast and efficient comparison-based sorting algorithm that uses a binary heap data structure. A heap is a special kind of complete binary tree where the parent node is always greater (in a Max Heap) or smaller (in a Min Heap) than its child nodes.

Heap Sort works by first converting the input array into a Max Heap, where the largest value is at the root. Then it repeatedly removes the largest element (the root), places it at the end of the array, and rebuilds the heap with the remaining elements. This process continues until all elements are sorted.

Key Concept: The Max Heap

A Max Heap is a binary tree that satisfies:

• Completeness: All levels are fully filled except possibly the last, which is filled from left to right.
• Heap property: Every parent node is greater than or equal to its children.

In Heap Sort, the array is treated as a binary tree using indices:

• Left child index = 2*i + 1
• Right child index = 2*i + 2
• Parent index = (i - 1) / 2

How Heap Sort Works

1. Build a Max Heap from the array.
2. Swap the first (maximum) element with the last element.
3. Reduce the heap size and heapify the root.
4. Repeat the process until the heap is empty.

Time and Space Complexity

• Space Complexity: O(1) → In-place sorting
• Stable: ❌ No (order of equal elements is not preserved)

When to Use Heap Sort

• When in-place sorting is needed
• When stable sort is not required
• When predictable performance of O(n log n) is important

Heap Sort – C++ Code Example

#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;       // Initialize largest as root
    int left = 2 * i + 1;  // Left child
    int right = 2 * i + 2; // Right child

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than current largest
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not the root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Main heap sort function
void heapSort(int arr[], int n) {
    // Step 1: Build Max Heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Step 2: Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // Call heapify on reduced heap
        heapify(arr, i, 0);
    }
}

// Utility function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
12 11 13 5 6 7 
Sorted array:
5 6 7 11 12 13 

Heap Sort – Visual Explanation (Step-by-Step)

Let’s sort the array:

[12, 11, 13, 5, 6, 7]

Step 1: Build Max Heap

Transform the array into a Max Heap:

• Initial heap: [13, 11, 12, 5, 6, 7]

(Heapify from bottom up — ensure all parent nodes are larger than their children)

Step 2: Extract Elements from Heap

Start extracting the max value (root of the heap):

1. Swap root with last → [7, 11, 12, 5, 6, 13]
   → Heapify → [12, 11, 7, 5, 6, 13]
2. Swap root with second last → [6, 11, 7, 5, 12, 13]
   → Heapify → [11, 6, 7, 5, 12, 13]
3. Continue until array is sorted.

Final Sorted Array

[5, 6, 7, 11, 12, 13]

Summary

• Heap Sort uses a binary heap to sort data efficiently.
• It performs O(n log n) consistently and in-place.
• It is not stable, but great for situations where memory is tight and performance is important.