Build Heap from Array Heapify in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the index of the left child in a heap array.

DSA Java

int leftChild(int i) {
    return 2 * i [1] 1;
}

Drag options to blanks, or click blank then click option'

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication or division incorrectly.

In a heap stored as an array, the left child of node at index i is at 2*i + 1.

2fill in blank

medium

Complete the code to swap two elements in the array.

DSA Java

void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[[1]];
    arr[[1]] = temp;
}

Drag options to blanks, or click blank then click option'

Aarr.length

Bi

C0

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index i for both assignments.

Using invalid indices like 0 or arr.length.

To swap elements at i and j, assign arr[i] = arr[j] and arr[j] = temp.

3fill in blank

hard

Fix the error in the heapify method to correctly heapify the subtree rooted at index i.

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] [1] arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

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

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>'.

Using equality or inequality operators incorrectly.

To maintain max-heap property, we check if left child is greater than current largest.

4fill in blank

hard

Fill both blanks to complete the buildHeap method that builds a max heap from an array.

DSA Java

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

Drag options to blanks, or click blank then click option'

An / 2 - 1

B0

Ci

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from 0 instead of n/2 - 1.

Passing wrong index to heapify.

We start heapifying from the last non-leaf node at n/2 - 1 down to 0, calling heapify at index i.

5fill in blank

hard

Fill all three blanks to complete the heap sort method using buildHeap and heapify.

DSA Java

void heapSort(int[] arr) {
    int n = arr.length;
    buildHeap(arr, n);

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

    // After sorting, the array is in ascending order
    // The root index is [3] for heapify after swap
}

Drag options to blanks, or click blank then click option'

A0

Bi

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop condition.

Heapifying wrong index after swap.

In heap sort, we swap root with last element, then heapify root (index 0) for reduced heap size i, looping until i > 0.

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