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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min-Heap after Build Heap from Array

What is the state of the array after building a min-heap using heapify on the array [4, 10, 3, 5, 1]?

DSA C++

void heapifyMin(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] < arr[smallest])
        smallest = left;
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        std::swap(arr[i], arr[smallest]);
        heapifyMin(arr, n, smallest);
    }
}

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

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = 5;
    buildMinHeap(arr, n);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

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

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

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

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

💡 Hint

Remember that heapify starts from the last non-leaf node and moves upward, ensuring the min-heap property.

The buildMinHeap function heapifies from the last non-leaf node to the root. After heapify, the smallest element is at the root, and the array represents a valid min-heap: [1, 4, 3, 5, 10].

❓ Predict Output

intermediate

Max-Heap Array after Build Heap

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

DSA C++

void heapifyMax(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) {
        std::swap(arr[i], arr[largest]);
        heapifyMax(arr, n, largest);
    }
}

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

int main() {
    int arr[] = {2, 7, 6, 3, 9};
    int n = 5;
    buildMaxHeap(arr, n);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

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

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

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

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

💡 Hint

Max-heap property means parent nodes are always greater than their children.

After building the max-heap, the largest element is at the root. The array becomes [9, 7, 6, 3, 2], which satisfies the max-heap property.

🔧 Debug

advanced

Identify the Bug in Heapify Function

What error will occur when running this heapify function on array [3, 1, 6, 5, 2, 4]?

DSA C++

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

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

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

A No error, outputs max-heap correctly

B Compilation error due to wrong syntax

C Stack overflow due to infinite recursion

D Array index out of bounds error

💡 Hint

Check how left and right child indices are calculated for a zero-based array.

The left and right child indices are incorrectly calculated for zero-based arrays. They should be 2*i + 1 and 2*i + 2. Using 2*i and 2*i + 1 causes out-of-bounds access.

🧠 Conceptual

advanced

Time Complexity of Build Heap

What is the time complexity of building a heap from an unsorted array of size n using the heapify method?

A O(log n)

B O(n log n)

C O(n)

D O(n^2)

💡 Hint

Consider that heapify is called on nodes from bottom to top and the work done decreases at lower levels.

Building a heap using heapify runs in O(n) time because the amount of work done at each level decreases exponentially, making the total work linear.

🚀 Application

expert

Final Heap Array after Multiple Heapify Calls

Given the array [8, 4, 7, 1, 3, 5, 6], after calling heapify on index 2 and then on index 0 (max-heap), what is the resulting array?

DSA C++

void heapifyMax(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) {
        std::swap(arr[i], arr[largest]);
        heapifyMax(arr, n, largest);
    }
}

int main() {
    int arr[] = {8, 4, 7, 1, 3, 5, 6};
    int n = 7;
    heapifyMax(arr, n, 2);
    heapifyMax(arr, n, 0);
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

A [8, 4, 7, 1, 3, 6, 5]

B ]6 ,5 ,3 ,1 ,7 ,4 ,8[

C [8, 4, 7, 1, 3, 5, 6]

D ]5 ,6 ,3 ,1 ,7 ,4 ,8[

💡 Hint

Heapify at index 2 swaps elements to maintain max-heap, then heapify at root fixes the heap.

Heapify at index 2 swaps 7 with 6 (right child), resulting in [8,4,7,1,3,6,5]. Then heapify at index 0 keeps 8 as largest, so array remains [8,4,7,1,3,6,5].

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 rearrange elements to satisfy the heap property

D. To reverse the array elements

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 this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange elements to satisfy the heap property -> Option C

4. Quick Check:

   Heapify = rearrange for heap property [OK]

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

easy

A. heapify(i, arr, n);

B. heapify(arr, i, n);

C. heapify(n, i, arr);

D. heapify(arr, n, i);

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

   heapify(arr, n, i); matches the standard signature: heapify(arr, n, i); others have wrong order.

3. Final Answer:

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

4. Quick Check:

   heapify(arr, size, index) = B [OK]

Hint: Remember: array, size, then index for heapify call [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, 0) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify root and children

   Index 0 has value 4; children at indices 1 and 2 are 10 and 3.

2. Step 2: Swap with largest child and heapify

   Swap 4 with 10 (largest child). Now at index 1, value 4 has children 5 and 1. Swap 4 with 5. Final array: [10, 5, 3, 4, 1]

3. Final Answer:

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

4. Quick Check:

   Max-heap root fixed = [10, 5, 3, 4, 1] [OK]

Hint: Swap root with largest child, then heapify child subtree [OK]

Common Mistakes:

• Not swapping with largest child
• Stopping after first swap
• Confusing min-heap with max-heap

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. Heapify should be called with index i+1

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

C. Loop should run from 0 to n-1

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building requires heapify from last non-leaf node down to root, i.e., from n/2 - 1 down to 0.

2. Step 2: Identify loop direction and range error

   The loop incorrectly goes from 0 up to n/2, which is wrong direction and range.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without decrement
• Calling heapify with wrong index

5. You have an array arr = [3, 9, 2, 1, 4, 5]. After building a max heap using the standard heapify method, what is the final array?

hard

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

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

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

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

Solution

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

   Last non-leaf index = n/2 -1 = 2. Heapify at index 2: children 5 and none, 2 < 5, swap to get [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 change.

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Swap 3 with 9: [9,3,5,1,4,2]. Heapify at index 1: value 3, children 1 and 4. Swap 3 with 4: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap built = [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up, swap with largest child repeatedly [OK]

Common Mistakes:

• Not heapifying all parents
• Swapping with wrong child
• Stopping heapify early