Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a special binary tree called a Heap (usually a Max-Heap or Min-Heap).

It is based on the Heap Data Structure, and it divides the array into two parts sorted and unsorted.

A Heap data structure is always a complete Binary Tree, which means all levels of the tree are fully filled.

Max-Heap: The parent is always greater than its children.
Min-Heap: The parent is always smaller than its children.

Heap sort uses a Max-Heap to sort in ascending order.

Heap Property

All nodes are either (greater than or equal to) or (less than or equal to) each of its children.

If the parent nodes are greater than their children, heap is called a Max-Heap, and if the parent nodes are small than their child nodes, heap is called Min-Heap.

How Heap Sort Works?

Build a Max-Heap from the input array.
Swap the root (largest) element with the last element of the array.
Reduce the heap size by 1 (last element is sorted).
Heapify the root again to maintain the max-heap property.
Repeat until the heap size is 1.

Example: Heap Sort

We'll visualize it as a binary tree and show the steps of building the Max-Heap and then sorting. [4, 10, 3, 5, 1]

Step 1: Build Max-Heap

Initial Binary Tree from Array

Heapify at index 1 (node = 10)

Left = 5, Right = 1 → 10 is already the largest → No change

Heapify at index 0 (node = 4)

Left = 10, Right = 3 → 10 is largest → Swap 4 and 10

Tree becomes

Heapify index 1 (node = 4)

Left = 5, Right = 1 → 5 is largest → Swap 4 and 5

Final Max-Heap Tree

Corresponding array: [10, 5, 3, 4, 1]

Step 2: Heap Sort Process

Swap root (10) with last element (1)

Array: [1, 5, 3, 4, 10]

Heapify first 4 elements
Tree before heapify (size 4)

Heapify root (1 → index 0)
Largest is 5 (index 1) → Swap 1 and 5

Heapify index 1 (node = 1) → 4 is larger → Swap 1 and 4

Swap root (5) with index 3 (1)

Array: [1, 4, 3, 5, 10]

Heapify first 3 elements
Tree before heapify (size 3)

      1
     / \
    4   3

Swap 1 and 4
Tree Become

      4
     / \
    1   3

Swap root (4) with index 2 (3)

Array: [3, 1, 4, 5, 10]

Heapify first 2 elements
Tree before heapify (size 2)

     3
    /
   1

Swap 3 and 1
Tree become

     1
    /
   3

Swap root (1) with index 1 (3)

Array becomes fully sorted: [1, 3, 4, 5, 10]

Initial Array as Tree

Max-Heap

When to Use Heap Sort?

When memory usage must be minimal.

When you want consistent performance regardless of input.

For large data files or data streams (external sorting).

When you need a priority queue behavior as part of sorting.

Algorithm for Heap Sort

Heap_Sort(arr, n):
1. Build a Max-Heap from the input array:
   a. For i from (n/2 - 1) down to 0:
        Call Heapify(arr, n, i)

2. Repeat for i from (n - 1) down to 1:
   a. Swap arr[0] with arr[i]  // Move max element to the end
   b. Reduce heap size by 1 (i = i - 1)
   c. Call Heapify(arr, i, 0)

-----------------------------------------------------

Heapify(arr, n, i):
1. Let largest = i
2. left = 2 * i + 1
3. right = 2 * i + 2

4. If left < n and arr[left] > arr[largest]:
       largest = left

5. If right < n and arr[right] > arr[largest]:
       largest = right

6. If largest ≠ i:
   a. Swap arr[i] and arr[largest]
   b. Call Heapify(arr, n, largest)

n is the number of elements in the array.
Heapify ensures the subtree rooted at index i satisfies the Max-Heap property.
The process of heapifying begins from the last non-leaf node (i.e., n/2 - 1) and goes up to the root.

Time and Space Complexity

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Space Complexity: O(1) (in-place sorting)

Stable: No (It does not preserve the order of equal elements)

Advantages of Heap Sort

Guaranteed O(n log n) time.

No extra memory needed (in-place).

Works well with large datasets.

Not affected by input order (uniform performance).

Disadvantages of Heap Sort

Slower than Quick Sort in practice (due to constant factors).

Not stable (equal elements may change order).

More complex than insertion or bubble sort.

C Program of Merge Sort

#include <stdio.h>

// 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 index
    int right = 2 * i + 2;// right child index

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

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

    // If largest is not root
    if (largest != i) {
        // Swap arr[i] and arr[largest]
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

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

// Main function to perform Heap Sort
void heapSort(int arr[], int n) {
    // Step 1: Build max heap (rearrange array)
    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
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

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

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver Code
int main() {
    int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    heapSort(arr, n);

    printf("Sorted array using Heap Sort:\n");
    printArray(arr, n);

    return 0;
}

Output

Original array:
16 14 10 8 7 9 3 2 4 1
Sorted array using Heap Sort:
1 2 3 4 7 8 9 10 14 16

Numerical Questions for Heap Sort

Sort the following array using Heap Sort [8, 3, 5, 4, 1, 2].
Perform Heap Sort on the array [9, 6, 7, 3, 2].
Sort the following array using Heap Sort and write the array after each root swap and heapify operation [25, 12, 16, 13, 10, 8, 14].
Construct a Max-Heap from the array and then sort it using Heap Sort [30, 20, 15, 5, 10, 12, 6, 40].
An array is given as [90, 70, 50, 30, 20, 10, 60]. Perform Heap Sort and display the result.
Heapify the array [40, 35, 30, 15, 10, 5, 25, 12] and sort it using Heap Sort. Show the tree structure at each step.
Apply Heap Sort on this array and trace the steps using both array and tree format [100, 19, 36, 17, 3, 25, 1, 2, 7].

Menu