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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output array after building a max heap?

Given the array [4, 10, 3, 5, 1], what is the array representation after applying the build max heap process?

DSA Java

int[] arr = {4, 10, 3, 5, 1};
// After build max heap, what is arr?

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

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

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

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

💡 Hint

Remember that build max heap rearranges the array so that each parent is greater than its children.

The build max heap process starts from the last non-leaf node and heapifies down. After heapifying, the array becomes [10, 5, 3, 4, 1].

❓ 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 representation after applying the build min heap process?

DSA Java

int[] arr = {7, 2, 6, 3, 9};
// After build min heap, what is arr?

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

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

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

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

💡 Hint

Build min heap ensures each parent is smaller than its children.

Heapify starts from last non-leaf node and moves upward, swapping to maintain min heap property. The final array is [2, 3, 6, 7, 9].

🔧 Debug

advanced

Does this heapify method cause an error when building a max heap?

What error will this Java heapify method cause when building a max heap?

DSA Java

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

void buildHeap(int[] arr) {
  int n = arr.length;
  for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

A StackOverflowError due to infinite recursion in heapify

B ArrayIndexOutOfBoundsException due to incorrect loop start in buildHeap

C No error, code runs correctly

D NullPointerException due to uninitialized array

💡 Hint

Does heapify access array elements without boundary checks? Examine the if conditions.

No error, the code runs correctly. The loop starts at n/2 - 1, which is the last non-leaf node, and heapify checks left < n and right < n before accessing arr[left] or arr[right], preventing out-of-bounds exceptions.

🧠 Conceptual

advanced

Why does build heap start heapifying from the middle of the array?

Why does the build heap algorithm start heapifying from the index n/2 - 1 instead of from index 0?

A Because heapifying from index 0 is inefficient and causes errors

B Because elements from n/2 to n-1 are leaf nodes and already satisfy heap property

C Because the array is sorted from n/2 to n-1

D Because heapify only works on the right half of the array

💡 Hint

Think about which nodes have children in a binary heap array.

Nodes from n/2 to n-1 are leaf nodes with no children, so they already satisfy heap property. Heapifying them is unnecessary.

🚀 Application

expert

What is the height of the heap built from an array of size 31?

If you build a complete binary heap from an array of size 31, what is the height of the heap?

A 4

B 6

C 5

D 31

💡 Hint

Height of a complete binary tree with n nodes is floor(log2(n)).

Height is the number of edges on the longest path from root to leaf. For 31 nodes (2^5 - 1), height = floor(log2(31)) = 4.

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 is a special tree-based structure 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 so that the heap property is maintained starting from a node down to its children.

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 heap property from a node down [OK]

Common Mistakes:

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

2. Which of the following is the correct way to start heapifying an array of size n in Java when building a max heap?

easy

A. for (int i = 0; i < n; i++) heapify(arr, i, n);

B. for (int i = n - 1; i >= 0; i--) heapify(arr, i, n);

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

D. for (int i = 1; i < n; i++) heapify(arr, i, n);

Solution

1. Step 1: Identify heapify start index

   Heapify starts from the last non-leaf node, which is at index n/2 - 1, moving upwards to root.

2. Step 2: Loop direction and range

   The loop runs backward from n/2 - 1 down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

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

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify from n/2 - 1 down to 0 [OK]

Common Mistakes:

• Starting heapify from index 0 upwards
• Heapifying leaf nodes unnecessarily
• Looping in wrong direction

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

medium

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

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

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

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

Solution

1. Step 1: Start heapify from index 1 (n/2 - 1)

   Heapify at index 1: children are 5 and 1. Max child is 5. Swap 10 and 5? No, 10 > 5, so no swap.

2. Step 2: Heapify at index 0

   At index 0: value 4, children 10 and 3. Max child is 10. Swap 4 and 10. Array becomes [10, 4, 3, 5, 1]. Now heapify at index 1 again.

3. Step 3: Heapify at index 1 again

   At index 1: value 4, children 5 and 1. Max child is 5. Swap 4 and 5. Array becomes [10, 5, 3, 4, 1].

4. Final Answer:

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

5. Quick Check:

   Max heap built correctly [OK]

Hint: Heapify bottom-up swaps to fix max heap [OK]

Common Mistakes:

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

4. Consider this heapify method snippet in Java:

void heapify(int[] arr, int i, int n) {
  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, largest, n);
  }
}

What is the bug if the method is called with heapify(arr, 0, arr.length - 1)?

medium

A. The size parameter should be arr.length, not arr.length - 1

B. The left and right child calculations are incorrect

C. The recursive call should be heapify(arr, i, n) instead of heapify(arr, largest, n)

D. The swap logic is missing

Solution

1. Step 1: Understand parameter n meaning

   Parameter n represents the size of the array segment to heapify, so it should be the length of the array.

2. Step 2: Identify off-by-one error

   Using arr.length - 1 excludes the last element, causing incorrect heapify behavior and possible index errors.

3. Final Answer:

   The size parameter should be arr.length, not arr.length - 1 -> Option A

4. Quick Check:

   Pass full length for heapify size [OK]

Hint: Pass full array length, not length minus one [OK]

Common Mistakes:

• Passing length - 1 as size
• Miscalculating child indices
• Incorrect recursive call parameters

5. You have an array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify, what will be the array? Also, explain why starting heapify from n/2 - 1 is efficient compared to starting from index 0.

hard

A. [9, 5, 4, 3, 2, 1]; starting from 0 is better for full coverage

B. [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes

C. [5, 9, 4, 3, 2, 1]; starting from n/2 - 1 is inefficient

D. [3, 9, 2, 1, 4, 5]; heapify does not change array order

Solution

1. Step 1: Build max heap from bottom up

   Start heapify at index 2 (n/2 - 1 = 6/2 - 1 = 2): - At index 2 (value 2), children: 5 (index 5), no right child. - Swap 2 and 5 -> [3, 9, 5, 1, 4, 2] Heapify at index 1: - Value 9, children 1 and 4, no swap. Heapify at index 0: - Value 3, children 9 and 5. - Swap 3 and 9 -> [9, 3, 5, 1, 4, 2] Heapify at index 1: - Value 3, children 1 and 4. - Swap 3 and 4 -> [9, 4, 5, 1, 3, 2]

2. Step 2: Explain efficiency of starting at n/2 - 1

   Nodes from n/2 to n-1 are leaf nodes with no children, so heapify on them is unnecessary. Starting at n/2 - 1 reduces calls and improves efficiency.

3. Final Answer:

   [9, 4, 5, 1, 3, 2]; starting from n/2 - 1 avoids unnecessary heapify on leaf nodes -> Option B

4. Quick Check:

   Heapify bottom-up skips leaves for efficiency [OK]

Hint: Heapify from last non-leaf node skips leaves [OK]

Common Mistakes:

• Heapifying leaf nodes unnecessarily
• Incorrect swaps during heapify
• Misunderstanding heapify start index