Heap Sort Algorithm, Program Explanations with Examples

🧑‍💻 By quescol • 📝 Updated on: 18 July 2025

Heap sort is an efficient sorting algorithm that uses heap data structure. The key idea behind heap sort is to transform the unsorted array into a heap structure, which is a complete binary tree. And then delete elements from the root of the heap in each iteration. The idea is to build a Min Heap from the unsorted array, and then repeatedly extract the minimum element from the heap that will be at root node and rebuild the heap until all elements are sorted.

There are two types of heaps: max heaps and min heaps. In a max heap, the parent node is always greater than its child nodes, while in a min heap, parent node will be always smaller than its child nodes.

Use of Max Heap vs Min Heap in Heap Sort

Heap Type	Sort Order Produced	How It Works
Max Heap	Ascending order	Extract the maximum element each time and move it to the end of the array.
Min Heap	Descending order	Extract the minimum element each time and move it to the end of the array.

How it works

1. Max Heap for Ascending Order

• Build a Max Heap.
• Place the maximum element at the end.
• Reduce heap size and repeat.

Example Output (Ascending):

[1, 3, 4, 5, 10]

2. Min Heap for Descending Order

• Build a Min Heap.
• Place the minimum element at the end.
• Reduce heap size and repeat.

Example Output (Descending):

[10, 5, 4, 3, 1]

What Heap Sort Algorithm Says (Standard Approach)?

1. Build a Max Heap from the unsorted array.
2. Repeat:
   • Swap the root (max element) with the last element of the heap.
   • Reduce the heap size (excluding the last sorted element).
   • Reheapify.
3. At the end, the array is sorted in-place from start to end.

✅ So, Heap Sort always puts the max element at the end during each iteration.

The heap sort algorithm consists of two main phases:

1. Building a Heap: Convert the array into a heap structure. Either in min heap or in max heap.
2. Heap Deletion / Sorting: Repeatedly remove the root element of the heap and re-heapify, resulting in a sorted array.

Heap Sort Algorithm

Pseudocode

HEAPSORT(arr):
    BUILD-MAX-HEAP(arr)
    for i = length(arr) - 1 down to 1:
        swap arr[0] with arr[i]
        heap_size = heap_size - 1
        MAX-HEAPIFY(arr, 0)

BUILD-MAX-HEAP(arr)

BUILD-MAX-HEAP(arr):
    heap_size = length(arr)
    for i = floor(heap_size / 2) - 1 downto 0:
        MAX-HEAPIFY(arr, i)

MAX-HEAPIFY(arr, i)

MAX-HEAPIFY(arr, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap arr[i] with arr[largest]
        MAX-HEAPIFY(arr, largest)

Analysis of Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. Here’s an analysis of Heap Sort.

Important Points about heap sort

1. Time Complexity:
   • Best Case, Average Case and Worst Case: O(n log n)
   • The time complexity is due to the heapify process, which is O(log n), repeated for n elements.
2. Space Complexity:
   • Worst Case: O(1) (Heap sort is an in-place algorithm)
   • No additional memory is needed apart from what is required to store the array.
3. Algorithm Type:
   • It is an in-place sorting algorithm but not a stable sort.
4. Binary Heap Utilization:
   • Heap sort uses the properties of a binary heap to sort the elements. A max heap is typically used for ascending order, and a min heap is used for descending order.

Operation	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)
Stability	❌ Not Stable

C Program: Heap Sort in Ascending Order (Using Max Heap)

#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 root with largest
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Main function to perform heap sort
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
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Call heapify on 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[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    heapSort(arr, n);

    printf("Sorted array (ascending): ");
    printArray(arr, n);

    return 0;
}

Output

[1, 3, 4, 5, 10]

Explanations (Dry Run Example with input: 4, 10, 3, 5, 1)

Goal: Sort the array using Heap Sort (Max Heap) and show the execution tree of the process (how the heap evolves step by step).

We’ll represent the array as a binary tree (heap) in each key step. Let’s break this down into two main phases:

Phase 1: Building the Max Heap

Initial Array:

[4, 10, 3, 5, 1]

We treat the array as a binary tree using index positions:

          4
        /   \
      10     3
     /  \
    5    1

Step 1: Heapify from index 1 (10)

• Left = 3 → 5
• Right = 4 → 1
• 10 > 5 and 10 > 1 → Already max heap here. No change.

          4
        /   \
      10     3
     /  \
    5    1

Step 2: Heapify from index 0 (4)

• Left = 1 → 10
• Right = 2 → 3
• 10 is largest → Swap with 4

Now:

         10
        /   \
       4     3
     /  \
    5    1

Now we heapify at index 1 (4)

• Left = 3 → 5
• Right = 4 → 1
• 5 is larger than 4 → swap

Final Max Heap:

         10
        /   \
       5     3
     /  \
    4    1

Array now:

[10, 5, 3, 4, 1]

Phase 2: Sorting by Extracting Max Elements

Step 1: Swap root with last element → 10 & 1

[1, 5, 3, 4, 10]

Heapify on index 0 (1):

• Left = 1 → 5
• Right = 2 → 3 → largest is 5 → swap

Now:

         5
        / \
       1   3
      /
     4

Heapify at index 1:

• Left = 3 → 4 → 4 > 1 → swap

         5
        / \
       4   3
      /
     1

Array:

[5, 4, 3, 1, 10]

Step 2: Swap root with 1 → 5 & 1

[1, 4, 3, 5, 10]

Heapify index 0:

• Left = 1 → 4
• Right = 2 → 3 → largest is 4 → swap

        4
       / \
      1   3

Array:

[4, 1, 3, 5, 10]

Step 3: Swap 4 & 3

[3, 1, 4, 5, 10]

Heapify index 0:

• Left = 1 → 1 (no change)

        3
       / \
      1   (ignore)

Array:

[3, 1, 4, 5, 10]

Step 4: Swap 3 & 1

[1, 3, 4, 5, 10]

Done. Sorted.

✅ Final Sorted Tree (Flat View):

[1, 3, 4, 5, 10]

Execution Tree Summary (Visually)

Here’s a simplified text tree format showing transitions:

Initial:
         4
       /   \
     10     3
    /  \
   5    1

After Building Max Heap:
         10
        /   \
       5     3
     /  \
    4    1

After extracting 10:
         5
        / \
       4   3
      /
     1

After extracting 5:
         4
        / \
       1   3

After extracting 4:
         3
        /
       1

After extracting 3:
         1

Advantages And Disadvantages of Heap Sort

Advantages of Heap Sort

1. Efficient for Large Data:
   • It is very efficient for large data sets due to its O(n log n) time complexity, which is better than O(n^2) for algorithms like bubble sort or insertion sort.
2. In-Place Sorting:
   • Requires a constant amount of space, making it space-efficient.
3. No Additional Memory:
   • Since it sorts in place, it does not require any extra memory for sorting, unlike merge sort.
4. Predictable Performance:
   • Heap sort provides a guaranteed O(n log n) performance, which is not the case with algorithms like quicksort (which can degrade to O(n^2) in the worst case).

Disadvantages of Heap Sort

1. Not Stable:
   • Heap sort is not a stable sort; equal elements might not retain their original order post-sorting.
2. Slower than Quick Sort and Merge Sort:
   • In practical scenarios, heap sort is often outperformed by other O(n log n) algorithms, like quick sort and merge sort, especially on smaller data sets or nearly sorted data sets.
3. Cache Performance:
   • Heap sort has poor cache performance compared to algorithms like quick sort, which can be more significant in modern computing.

FAQs

1. Is Heap Sort Suitable for All Types of Data?
   • Heap sort is generally suitable for most types of data, especially if consistent O(n log n) performance is needed.
2. Why is Heap Sort Not Stable?
   • During sorting, elements might be swapped in a manner that changes the relative order of equal elements.
3. Can Heap Sort Be Used for Linked Lists?
   • While possible, heap sort is not efficient for linked lists due to the lack of random access capabilities.
4. How Does Heap Sort Compare to Quick Sort?
   • Heap sort has better worst-case time complexity (O(n log n)) compared to quick sort’s O(n^2), but quick sort is often faster in practice and more cache-efficient.
5. Is Heap Sort Good for Large Arrays?
   • Yes, it’s particularly effective for large arrays due to its efficient handling of large data sets and its consistent performance regardless of the input data’s order.

In summary, heap sort is a reliable and efficient sorting algorithm for large datasets and situations where consistent O(n log n) performance is crucial. However, its practical performance and lack of stability might make other algorithms like quick sort or merge sort preferable in certain scenarios.