Build Heap from Array Heapify in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output array after heapifying?

Given the array [4, 10, 3, 5, 1], what is the array after building a max heap using heapify?

DSA C

int arr[] = {4, 10, 3, 5, 1};
int n = 5;
// Build max heap code runs here
// Output the array after heapify

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

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

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

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

💡 Hint

Remember max heap means parent nodes are greater than children.

Heapify rearranges the array so that the largest element is at the root and the heap property is maintained for all nodes.

❓ Predict Output

intermediate

What is the output array after building a min heap?

Given the array [7, 2, 6, 3, 9], what is the array after building a min heap using heapify?

DSA C

int arr[] = {7, 2, 6, 3, 9};
int n = 5;
// Build min heap code runs here
// Output the array after heapify

A [2, 3, 6, 7, 9]

B [3, 2, 6, 7, 9]

C [2, 7, 6, 3, 9]

D [7, 2, 6, 3, 9]

💡 Hint

Min heap means parent nodes are smaller than children.

Heapify rearranges the array so that the smallest element is at the root and the heap property is maintained for all nodes.

🧠 Conceptual

advanced

Why do we start heapify from the last non-leaf node?

In building a heap from an array, why do we start heapify from the last non-leaf node and move upwards?

A Because heapify only works on leaf nodes.

B Because starting from the root would cause infinite loops.

C Because leaf nodes are already heaps and don't need heapify.

D Because the last non-leaf node is always the smallest element.

💡 Hint

Think about which nodes have children.

Leaf nodes have no children, so they already satisfy the heap property. Starting from the last non-leaf node ensures all subtrees become heaps.

🔧 Debug

advanced

What error occurs in this heapify code snippet?

Consider this C code snippet for heapify: 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 error will happen if n is zero?

A Stack overflow due to infinite recursion.

B No error, function returns immediately.

C Array index out of bounds error.

D Segmentation fault due to invalid memory access.

💡 Hint

Check the conditions before accessing array elements.

If n is zero, left and right will be greater than or equal to n, so no recursive call happens and function returns safely.

🚀 Application

expert

How many swaps are needed to build a max heap from [1, 3, 5, 7, 9, 2]?

Using the standard heapify method to build a max heap from the array [1, 3, 5, 7, 9, 2], how many swaps will occur during the entire build heap process?

A 4

B 6

C 5

D 3

💡 Hint

Simulate heapify from last non-leaf node upwards and count swaps.

Heapify swaps occur when a parent is smaller than a child. Counting swaps carefully during build heap gives 3 swaps total.

Practice

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

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

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

Solution

1. Step 1: Understand heap property

   A heap is a special tree where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

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

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [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 heapify on an array arr of size n starting from index i in C?

easy

A. heapify(i, arr, n);

B. heapify(arr, n, i);

C. heapify(n, arr, i);

D. heapify(arr, i, n);

Solution

1. Step 1: Understand heapify parameters

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

2. Step 2: Match correct syntax

   Calling heapify(arr, n, i); matches the standard parameter order: array, size, index.

3. Final Answer:

   heapify(arr, n, i); -> Option B

4. Quick Check:

   Function call order = arr, size, index [OK]

Hint: Remember: array first, then size, then index [OK]

Common Mistakes:

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

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

medium

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

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

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

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

Solution

1. Step 1: Identify children of index 1

   Index 1 has children at indices 3 and 4 with values 5 and 1.

2. Step 2: Compare and swap if needed

   Value at index 1 is 10, which is greater than both children, so no swap needed.

3. Final Answer:

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

4. Quick Check:

   Parent >= children, no change [OK]

Hint: Check parent vs children, swap only if smaller [OK]

Common Mistakes:

• Swapping when parent is already largest
• Mixing up child indices
• Assuming heapify sorts entire array

4. Consider this code snippet to build a max heap from array arr of size n. Identify the error:

for (int i = 0; i <= n/2; i++) {
    heapify(arr, n, i);
}

medium

A. Loop should start from n/2 - 1 and go down to 0

B. Loop should start from 0 and go to n - 1

C. heapify function parameters are incorrect

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building starts from last non-leaf node at index n/2 - 1 down to 0.

2. Step 2: Check loop direction and range

   Loop incorrectly goes up from 0 to n/2, should go down from n/2 - 1 to 0.

3. Final Answer:

   Loop should start from n/2 - 1 and go down to 0 -> Option A

4. Quick Check:

   Build heap loops down from n/2-1 [OK]

Hint: Build heap loops backward from last parent [OK]

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without going down
• Incorrect heapify parameters

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

hard

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

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

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

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

Solution

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

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

2. Step 2: Heapify at index 1

   Index 1 value 9, children 1 and 4. 9 is largest, no swap -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Largest is 9 at index 1, swap -> [9,3,5,1,4,2]. Heapify at index 1 again: 3 with children 1 and 4, largest is 4 at index 4, swap -> [9,4,5,1,3,2]

4. Final Answer:

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

5. Quick Check:

   Bottom-up heapify fixes subtree order [OK]

Hint: Heapify bottom-up swaps parents with largest child [OK]

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early