Heap Sort Algorithm in DSA C

Mental Model

Heap sort organizes data into a special tree structure called a heap, then repeatedly removes the largest item to sort the list.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. You keep taking the biggest book off the pile and placing it in order to get a sorted stack.

Array: [4, 10, 3, 5, 1]
Heap (max-heap):
       10
      /  \
     5    3
    / \
   4   1

Dry Run Walkthrough

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

Goal: Sort the array in ascending order using heap sort

Step 1: Build max heap from array

[10, 5, 3, 4, 1]

Why: We rearrange the array so the largest element is at the root (index 0)

Step 2: Swap root (10) with last element (1), reduce heap size

[1, 5, 3, 4, 10]

Why: Place the largest element at the end of the array and exclude it from heap

Step 3: Heapify root to restore max heap

[5, 4, 3, 1, 10]

Why: Fix heap so the largest element is again at root

Step 4: Swap root (5) with last element in heap (1), reduce heap size

[1, 4, 3, 5, 10]

Why: Move next largest element to its correct position

Step 5: Heapify root to restore max heap

[4, 1, 3, 5, 10]

Why: Restore heap property for remaining elements

Step 6: Swap root (4) with last element in heap (3), reduce heap size

[3, 1, 4, 5, 10]

Why: Place next largest element in sorted position

Step 7: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is already valid, no change

Step 8: Swap root (3) with last element in heap (1), reduce heap size

[1, 3, 4, 5, 10]

Why: Place next largest element in sorted position

Step 9: Heapify root to restore max heap

[3, 1, 4, 5, 10]

Why: Heap property is valid with one element, no change

Result:

[1, 3, 4, 5, 10] -- sorted array in ascending order

Annotated Code

DSA C

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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 < n && arr[left] > arr[largest])
        largest = left; // left child is larger

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

    if (largest != i) {
        swap(&arr[i], &arr[largest]); // swap root with largest child
        heapify(arr, n, largest); // recursively heapify affected subtree
    }
}

void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i); // heapify from bottom up
    }

    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // move current root to end
        heapify(arr, i, 0); // heapify reduced heap
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i != n - 1) printf(" -> ");
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    heapSort(arr, n);

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

    return 0;
}

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

build max heap from bottom non-leaf nodes up

for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); }

extract max element to end and restore heap

if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); }

swap root with largest child and heapify subtree

Output

Original array:

4 -> 10 -> 3 -> 5 -> 1

Sorted array:

1 -> 3 -> 4 -> 5 -> 10

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n extraction steps takes O(log n) to heapify

Space: O(1) because heap sort sorts the array in place without extra storage

vs Alternative: Compared to simple sorts like bubble sort with O(n^2), heap sort is much faster for large data sets

Edge Cases

empty array

no operations performed, output remains empty

DSA C

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

array with one element

heapify runs once but no swaps needed, array remains same

DSA C

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

array with duplicate elements

duplicates are handled normally, sorted output includes duplicates

DSA C

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

When to Use This Pattern

When you need to sort data efficiently in place and can use a tree-like structure, heap sort is a good choice because it uses a max heap to repeatedly extract the largest element.

Common Mistakes

Mistake: Not building the max heap correctly before sorting
Fix: Make sure to heapify all non-leaf nodes starting from n/2 - 1 down to 0

Mistake: Not reducing the heap size after swapping the root with the last element
Fix: After swapping, call heapify with the reduced heap size to exclude sorted elements

Summary

Heap sort sorts an array by building a max heap and repeatedly extracting the largest element.

Use heap sort when you want an efficient in-place sorting algorithm with O(n log n) time.

The key insight is to maintain the heap property so the largest element is always at the root for easy extraction.

Practice

1. What is the main purpose of the heapify process in the Heap Sort Algorithm?

easy

A. To build a max heap or min heap from an unsorted array

B. To swap the first and last elements of the array

C. To reverse the array elements

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   Heapify rearranges elements to satisfy heap property (max or min heap).

2. Step 2: Connect heapify to heap sort

   Heap sort uses heapify to build the heap before sorting.

3. Final Answer:

   To build a max heap or min heap from an unsorted array -> Option A

4. Quick Check:

   Heapify builds heap = To build a max heap or min heap from an unsorted array [OK]

Hint: Heapify creates heap structure from array [OK]

Common Mistakes:

• Confusing heapify with swapping elements
• Thinking heapify reverses the array
• Assuming heapify counts elements

2. Which of the following is the correct way to swap two elements arr[i] and arr[j] in C during heap sort?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr[i], arr[j] = arr[j], arr[i];

Solution

1. Step 1: Recall C swap syntax

   In C, swapping requires a temporary variable to hold one value.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses temp variable correctly; others are invalid in C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C = temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Trying Python-style swap syntax in C
• Assigning without temp causing overwrite
• Using undefined swap function

3. What will be the output array after applying heap sort on arr = [4, 10, 3, 5, 1]?

medium

A. [1, 4, 3, 5, 10]

B. [10, 5, 4, 3, 1]

C. [1, 3, 4, 5, 10]

D. [5, 10, 4, 3, 1]

Solution

1. Step 1: Build max heap from array

   Max heap of [4,10,3,5,1] rearranges to [10,5,3,4,1].

2. Step 2: Extract max and sort

   Repeatedly swap max with last element and heapify to get sorted array [1,3,4,5,10].

3. Final Answer:

   [1, 3, 4, 5, 10] -> Option C

4. Quick Check:

   Heap sort output = sorted array ascending = [1, 3, 4, 5, 10] [OK]

Hint: Heap sort outputs sorted ascending array [OK]

Common Mistakes:

• Confusing max heap with sorted array
• Forgetting to heapify after swaps
• Assuming heap sort outputs descending order

4. Identify the error in this heap sort snippet in C:

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2*i;
  int right = 2*i + 1;
  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);
  }
}

medium

A. The recursive call to heapify is missing

B. The swap logic is incorrect

C. The base case for recursion is missing

D. Left and right child indices should be 2*i + 1 and 2*i + 2

Solution

1. Step 1: Check child index calculation

   In 0-based arrays, left child = 2*i + 1, right child = 2*i + 2.

2. Step 2: Verify other parts

   Swap and recursion are correct; base case is implicit by condition checks.

3. Final Answer:

   Left and right child indices should be 2*i + 1 and 2*i + 2 -> Option D

4. Quick Check:

   Child indices in 0-based heap = 2*i+1, 2*i+2 [OK]

Hint: Remember 0-based heap child indices [OK]

Common Mistakes:

• Using 1-based indexing formulas in 0-based arrays
• Ignoring recursive heapify call
• Misplacing swap logic

5. Given an array with many duplicate elements, how does heap sort behave compared to quicksort in terms of stability and performance?

hard

A. Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²)

B. Heap sort is stable and faster than quicksort always

C. Heap sort is stable but slower than quicksort in all cases

D. Heap sort and quicksort are both stable and have same worst-case time

Solution

1. Step 1: Understand stability of heap sort

   Heap sort is not stable because it swaps elements without preserving order of equal keys.

2. Step 2: Compare performance with quicksort

   Heap sort guarantees O(n log n) time always; quicksort is faster on average but can degrade to O(n²).

3. Final Answer:

   Heap sort is not stable but has consistent O(n log n) time; quicksort is unstable and may degrade to O(n²) -> Option A

4. Quick Check:

   Heap sort stable? No; Time? O(n log n) always [OK]

Hint: Heap sort stable? No; quicksort worst-case O(n²) [OK]

Common Mistakes:

• Assuming heap sort is stable
• Thinking quicksort worst-case is always O(n log n)
• Confusing stability with speed