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].