Heap Sort Algorithm in DSA C#

Mental Model

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

Analogy: Imagine a pile of books stacked so the biggest book is always on top. You keep taking the biggest book off the top and placing it aside, ending up with a neat stack from smallest to biggest.

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 value is at the root to prepare for sorting

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

[1, 5, 3, 4, 10]

Why: Move the largest element to its correct final position at the end

Step 3: Heapify root to restore max heap property

[5, 4, 3, 1, 10]

Why: Fix the heap after removing the largest element to find the next largest

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

[1, 4, 3, 5, 10]

Why: Place the next largest element in its final position

Step 5: Heapify root to restore max heap property

[4, 1, 3, 5, 10]

Why: Restore heap to find next largest element

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 final position

Step 7: Heapify root to restore max heap property

[3, 1, 4, 5, 10]

Why: Heap is already valid, no change needed

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 final position

Step 9: Heapify root to restore max heap property

[1, 3, 4, 5, 10]

Why: Heap size is 1, no heapify needed

Result:

[1, 3, 4, 5, 10]

Annotated Code

DSA C#

using System;

class HeapSort {
    // Function to heapify a subtree rooted with node i which is an index in array[]
    static void Heapify(int[] array, 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 && array[left] > array[largest])
            largest = left;

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

        // If largest is not root
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;

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

    // Main function to do heap sort
    static void HeapSortAlgorithm(int[] array) {
        int n = array.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            Heapify(array, n, i);
        }

        // One by one extract elements
        for (int i = n - 1; i >= 0; i--) {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // call max heapify on the reduced heap
            Heapify(array, i, 0);
        }
    }

    static void PrintArray(int[] array) {
        for (int i = 0; i < array.Length; i++) {
            Console.Write(array[i]);
            if (i != array.Length - 1) Console.Write(", ");
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] array = {4, 10, 3, 5, 1};
        HeapSortAlgorithm(array);
        PrintArray(array);
    }
}

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

Build max heap by heapifying from bottom non-leaf nodes up

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

Swap root with last element, reduce heap size, then heapify root to restore max heap

if (largest != i) { swap and recursive Heapify }

If root is not largest, swap with largest child and heapify affected subtree

Output

1, 3, 4, 5, 10

Complexity Analysis

Time: O(n log n) because building the heap takes O(n) and each of the n elements is heapified in O(log n)

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

vs Alternative: Heap sort is more efficient than simple sorts like bubble sort (O(n^2)) and does not require extra space like merge sort (O(n))

Edge Cases

Empty array

No operations happen, output is empty

DSA C#

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

Array with one element

Heapify runs but no swaps needed, array remains same

DSA C#

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

Array with duplicate elements

Duplicates are handled normally, sorted output includes duplicates

DSA C#

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

When to Use This Pattern

When you need a reliable in-place sorting method with guaranteed O(n log n) time, reach for heap sort because it uses a heap structure to efficiently find the next largest element.

Common Mistakes

Mistake: Not building the max heap before sorting
Fix: Add the initial heap building loop before extracting elements

Mistake: Not reducing heap size after swapping root with last element
Fix: Pass the reduced heap size to Heapify to avoid including sorted elements

Mistake: Incorrect child index calculation (left = 2*i, right = 2*i+1)
Fix: Use zero-based indexing: left = 2*i + 1, right = 2*i + 2

Summary

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

Use heap sort when you want an in-place, comparison-based sort with guaranteed O(n log n) time.

The key insight is to organize data as a max heap so the largest element is always at the root for easy extraction.

Practice

1. What is the main purpose of the heapify function in the Heap Sort algorithm?

easy

A. To build a max heap from an unordered array

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

C. To reverse the array after sorting

D. To count the number of elements in the array

Solution

1. Step 1: Understand heapify's role

   The heapify function rearranges elements to satisfy the max heap property, where each parent node is greater than its children.

2. Step 2: Connect heapify to building max heap

   Heapify is called repeatedly to build a max heap from an unordered array before sorting begins.

3. Final Answer:

   To build a max heap from an unordered array -> Option A

4. Quick Check:

   heapify builds max heap = A [OK]

Hint: Heapify creates max heap structure before sorting [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. swap(arr[i], arr[j]);

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

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

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

Solution

1. Step 1: Identify correct C# swap syntax

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

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable correctly. arr[i], arr[j] = arr[j], arr[i]; is Python syntax. swap(arr[i], arr[j]); is invalid without a swap method. arr[i] = arr[j]; arr[j] = arr[i]; overwrites values incorrectly.

3. Final Answer:

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

4. Quick Check:

   Use temp variable to swap in C# = C [OK]

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

Common Mistakes:

• Using Python tuple swap syntax in C#
• Calling undefined swap function
• Overwriting values without temp variable

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

medium

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

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

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

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

Solution

1. Step 1: Build max heap from array

   Starting array: [4, 10, 3, 5, 1]. Max heap after heapify: [10, 5, 3, 4, 1].

2. Step 2: Extract max and sort

   Swap 10 with last element, heapify reduced heap: [5, 4, 3, 1, 10]. Repeat until sorted: final sorted array is [1, 3, 4, 5, 10].

3. Final Answer:

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

4. Quick Check:

   Heap sort sorts 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:

void HeapSort(int[] arr) {
  int n = arr.Length;
  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, n, 0);
  }
}

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 swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;
    Heapify(arr, n, largest);
  }
}

medium

A. Heapify call inside second loop uses wrong size parameter

B. The first for loop should start from n/2, not n/2 - 1

C. The second for loop condition should be i >= 0, not i > 0

D. Swap logic inside Heapify is incorrect

Solution

1. Step 1: Examine the second loop's Heapify call

   After swapping arr[0] and arr[i], the effective heap size is i. However, the code calls Heapify(arr, n, 0), using the original full size n instead of the reduced size i. This is the error.

2. Step 2: Confirm other options are not errors

   The first for loop should start from n/2, not n/2 - 1 is incorrect because it correctly starts at n/2 - 1. The second for loop condition should be i >= 0, not i > 0 is wrong because i > 0 is appropriate. Swap logic inside Heapify is incorrect is false; the swap is correct.

3. Final Answer:

   Heapify call inside second loop uses wrong size parameter -> Option A

4. Quick Check:

   Heapify in extract phase uses reduced size i, not n = B [OK]

Hint: Check loop bounds and heapify size carefully [OK]

Common Mistakes:

• Changing loop start incorrectly
• Using wrong loop end condition
• Misunderstanding heap size in heapify

5. Given a large array with many duplicate values, which modification to the standard heap sort algorithm can improve its stability (preserving order of equal elements)?

hard

A. Use a min heap instead of a max heap

B. Sort the array twice with heap sort

C. Add an index field to elements and compare indices when values are equal

D. Skip heapify calls for duplicate values

Solution

1. Step 1: Understand stability in sorting

   Stability means equal elements keep their original order after sorting.

2. Step 2: Analyze heap sort stability

   Standard heap sort is not stable because heap operations can reorder equal elements arbitrarily.

3. Step 3: Find modification to improve stability

   Adding an index field and comparing indices when values are equal preserves original order, making heap sort stable.

4. Final Answer:

   Add an index field to elements and compare indices when values are equal -> Option C

5. Quick Check:

   Use index to preserve order for stability = D [OK]

Hint: Use original indices to maintain stability in heap sort [OK]

Common Mistakes:

• Thinking min heap makes sort stable
• Skipping heapify breaks heap property
• Sorting twice wastes time without stability