Build Heap from Array Heapify in DSA C# - Build from Scratch

Build Heap from Array using Heapify

📖 Scenario: You are working on a program that manages a priority queue using a heap. You have an unordered array of numbers and want to convert it into a max heap efficiently.A max heap is a special tree where each parent node is greater than or equal to its children. This helps quickly find the largest number.

🎯 Goal: Build a max heap from the given array using the heapify process. You will write code to create the array, set up the heap size, implement the heapify function, and then apply it to build the heap.

📋 What You'll Learn

Create an integer array called arr with the exact values: 4, 10, 3, 5, 1

Create an integer variable heapSize and set it to the length of arr

Write a method Heapify that takes the array, heap size, and an index, and rearranges the elements to maintain max heap property

Use a for loop to call Heapify from the last parent node down to the root

Print the array after building the heap to show the max heap order

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and efficient sorting algorithms like heap sort.

💼 Career

Understanding heap construction and heapify is important for software engineers working on performance-critical applications and data processing.

1

Create the array

Create an integer array called arr with these exact values: 4, 10, 3, 5, 1

DSA C#

# Your code here

Hint

Use int[] arr = {4, 10, 3, 5, 1}; to create the array.

2

Set heap size variable

Create an integer variable called heapSize and set it to the length of the array arr

DSA C#

int[] arr = {4, 10, 3, 5, 1};
# Your code here

Hint

Use int heapSize = arr.Length; to get the array length.

3

Write the Heapify method

Write a method called Heapify that takes parameters int[] arr, int heapSize, and int i. Inside, implement the logic to maintain the max heap property by comparing the parent at index i with its left and right children and swapping if needed.

DSA C#

int[] arr = {4, 10, 3, 5, 1};
int heapSize = arr.Length;

// Write Heapify method here
# Your code here

Hint

Use recursion to call Heapify again if a swap happens.

4

Build the heap and print the array

Use a for loop with variable i starting from heapSize / 2 - 1 down to 0 (inclusive) to call Heapify(arr, heapSize, i). Then print the array arr elements separated by spaces on one line.

DSA C#

int[] arr = {4, 10, 3, 5, 1};
int heapSize = arr.Length;

void Heapify(int[] arr, int heapSize, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  arr[largest])
    {
        largest = left;
    }

    if (right  arr[largest])
    {
        largest = right;
    }

    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        Heapify(arr, heapSize, largest);
    }
}

// Build heap and print array
# Your code here

Hint

Start from the last parent node at heapSize / 2 - 1 and call Heapify down to index 0. Then print all elements separated by spaces.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To rearrange the array elements to satisfy the heap property

B. To sort the array in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap must satisfy the heap property where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   The heapify process rearranges elements to ensure this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option A

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree to maintain heap order [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min element
• Assuming heapify reverses the array

2. Which of the following is the correct way to call the Heapify method in C# for an array arr of size n at index i?

easy

A. Heapify(arr, n, i);

B. Heapify(i, arr, n);

C. Heapify(n, i, arr);

D. Heapify(arr, i, n);

Solution

1. Step 1: Check method signature

   Heapify usually takes the array, its size, and the index to heapify as parameters in that order.

2. Step 2: Match parameters order

   Heapify(arr, n, i); matches the correct order: array, size, index.

3. Final Answer:

   Heapify(arr, n, i); -> Option A

4. Quick Check:

   Heapify(arr, n, i) correct call [OK]

Hint: Remember parameter order: array, size, index [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. Given the array [4, 10, 3, 5, 1], what will be the array after calling Heapify(arr, 5, 1) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify node at index 1

   Value is 10, children at indices 3 (5) and 4 (1).

2. Step 2: Check heap property

   10 is greater than both children, so no swaps needed.

3. Final Answer:

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

4. Quick Check:

   Parent 10 > children 5,1 so unchanged [OK]

Hint: Check parent vs children values before swapping [OK]

Common Mistakes:

• Swapping when parent is already largest
• Confusing indices of children
• Assuming heapify sorts entire array

4. Consider this code snippet for heapify in C#:

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);
  }
}

What is the bug if the recursive call is missing?

medium

A. Stack overflow error will occur

B. Array will be sorted incorrectly

C. No bug, code works fine

D. Heap property may not be restored in subtrees

Solution

1. Step 1: Understand recursive call role

   After swapping, heapify must be called on the affected child subtree to fix heap property there.

2. Step 2: Effect of missing recursion

   Without recursion, only the root node is fixed, subtrees may remain invalid heaps.

3. Final Answer:

   Heap property may not be restored in subtrees -> Option D

4. Quick Check:

   Missing recursion breaks heap property below swapped node [OK]

Hint: Always recurse after swap to fix subtree [OK]

Common Mistakes:

• Assuming one swap fixes entire heap
• Thinking missing recursion causes crash
• Ignoring subtree heap violations

5. You have the array [3, 9, 2, 1, 4, 5]. After building a max-heap using the heapify method from the bottom up, what is the final array?

hard

A. [9, 4, 5, 3, 1, 2]

B. [9, 4, 5, 1, 3, 2]

C. [9, 3, 5, 1, 4, 2]

D. [9, 5, 4, 3, 1, 2]

Solution

1. Step 1: Start heapify from last non-leaf node

   Last non-leaf node index = (6/2)-1 = 2. Heapify at index 2 (value 2): children 5 (index 5), no right child. Swap 2 and 5 -> [3,9,5,1,4,2]

2. Step 2: Heapify at index 1 (value 9)

   Children 1 (index 3), 4 (index 4). 9 is largest, no change -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0 (value 3)

   Children 9 (index 1), 5 (index 2). Largest is 9, swap 3 and 9 -> [9,3,5,1,4,2]. Now heapify at index 1 (value 3): children 1 and 4. Largest is 4, swap 3 and 4 -> [9,4,5,1,3,2]

4. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option B

5. Quick Check:

   Bottom-up heapify gives max-heap [OK]

Hint: Heapify bottom-up from last non-leaf node [OK]

Common Mistakes:

• Not heapifying all non-leaf nodes
• Swapping incorrectly with children
• Stopping heapify too early