Heap Sort Algorithm, Program Explanations with Examples

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.

Quescol 1-Minute Read

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It first builds a Max Heap (for ascending order) where the largest element is always at the root. Then, it repeatedly removes the root (largest element) and places it at the end of the array, while rebuilding the heap each time to maintain the heap property.

Heap Sort has a time complexity of O(n log n) in the best, average, and worst cases, making it efficient for large datasets. It also uses only O(1) extra space, meaning it sorts in place without requiring additional memory. However, unlike Merge Sort, it is not stable, which means equal elements may not maintain their original order after sorting.

Important Heap Sort Points:

• Works on the heap data structure.
• Time complexity: O(n log n) for all cases.
• In-place sorting algorithm (needs no extra memory).
• Not stable but very efficient for large data.
• Commonly used in system-level sorting and priority queue operations.

Let’s Understand in Depth

What is Heap Sort?

Heap Sort is a sorting method that arranges numbers in order (smallest to largest or largest to smallest) using a special data structure called a heap.

A heap is like a tree where each parent has a specific rule —

• In a max heap, every parent is bigger than its children.
• In a min heap, every parent is smaller than its children.

Heap Sort first builds this heap structure from the array, then keeps removing the largest (or smallest) element one by one and puts it in the correct place. In the end, all elements become sorted.

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 from the array.
• Move the largest element (top of the heap) to the end of the array.
• Reduce the heap size and repeat the steps until the array is sorted.

Example Output (Ascending):

[1, 3, 4, 5, 10]

2. Min Heap for Descending Order

• Build a Min Heap from the array.
• Move the smallest element (top of the heap) to the end of the array.
• Reduce the heap size and repeat the steps until the array is sorted in descending order.

Example Output (Descending):

[10, 5, 4, 3, 1]

What Heap Sort Algorithm Says?

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²) 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²) 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.

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.