C Program for Heap Sort with Example and Explanation

A C program for heap sort builds a max heap using heapify and then repeatedly swaps the root with the last element, reducing heap size and calling heapify again; the core code includes functions heapify and heapSort to perform these steps.

Examples

Input5 12 11 13 5 6

Output5 5 6 11 12 13

Input4 10 3 5 1

Output1 3 4 5 10

Input1

Output1

How to Think About It

Heap sort works by first arranging the array into a max heap, where the largest value is at the root. Then, it swaps the root with the last element and reduces the heap size, repeating the process to sort the array in ascending order.

Algorithm

1

Build a max heap from the input array.

2

Swap the root (largest element) with the last element of the heap.

3

Reduce the heap size by one.

4

Call heapify on the root to restore max heap property.

5

Repeat steps 2-4 until the heap size is 1.

Code

c

#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[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Output

5 6 7 11 12 13 

Dry Run

Let's trace the array {12, 11, 13, 5, 6, 7} through heap sort.

1

Build max heap

Heapify nodes from index 2 to 0, resulting in max heap: {13, 11, 12, 5, 6, 7}

2

Swap root with last element

Swap 13 and 7, array becomes {7, 11, 12, 5, 6, 13}

3

Heapify root

Heapify index 0, max heap becomes {12, 11, 7, 5, 6, 13}

4

Repeat swap and heapify

Swap 12 and 6, heapify root: {11, 6, 7, 5, 12, 13}

5

Continue until sorted

Final sorted array: {5, 6, 7, 11, 12, 13}

Step	Array State
Build max heap	13 11 12 5 6 7
Swap root with last	7 11 12 5 6 13
Heapify root	12 11 7 5 6 13
Swap root with last	6 11 7 5 12 13
Heapify root	11 6 7 5 12 13
Swap root with last	5 6 7 11 12 13
Heapify root	7 6 5 11 12 13
Swap root with last	5 6 7 11 12 13
Heapify root	6 5 7 11 12 13
Swap root with last	5 6 7 11 12 13
Heapify root	5 6 7 11 12 13

Why This Works

Step 1: Building the max heap

We use heapify starting from the middle of the array to ensure each subtree satisfies the max heap property, placing the largest element at the root.

Step 2: Swapping root with last element

The root holds the largest value, so we swap it with the last element to move it to its correct sorted position.

Step 3: Restoring heap after swap

After swapping, we call heapify on the root to restore the max heap property for the reduced heap.

Alternative Approaches

Using Min Heap for descending order

c

#include <stdio.h>

void minHeapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
        minHeapify(arr, n, smallest);
    }
}

void heapSortDesc(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        minHeapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        minHeapify(arr, i, 0);
    }
}

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

    heapSortDesc(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

This approach sorts the array in descending order by building a min heap instead of a max heap.

Using iterative heapify

c

#include <stdio.h>

void heapifyIterative(int arr[], int n, int i) {
    int largest = i;
    while (1) {
        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;
            i = largest;
        } else {
            break;
        }
    }
}

void heapSortIterative(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapifyIterative(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapifyIterative(arr, i, 0);
    }
}

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

    heapSortIterative(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

This uses an iterative version of heapify to avoid recursion, which can be better for large arrays or limited stack.

Complexity: O(n log n) time, O(1) space

Time Complexity

Building the heap takes O(n) time, and each of the n-1 removals requires O(log n) time to heapify, resulting in O(n log n) overall.

Space Complexity

Heap sort sorts the array in place, so it uses O(1) extra space.

Which Approach is Fastest?

Heap sort is efficient and consistent with O(n log n) time, but quicksort is often faster in practice; iterative heapify can reduce recursion overhead.

Approach	Time	Space	Best For
Heap Sort (recursive heapify)	O(n log n)	O(1)	Stable performance, in-place sorting
Heap Sort (iterative heapify)	O(n log n)	O(1)	Avoid recursion overhead, large data
Min Heap for descending order	O(n log n)	O(1)	Sorting in descending order