Build Heap from Array Heapify in DSA C++ - Build from Scratch

Build Heap from Array using Heapify

📖 Scenario: You are working on a program that manages a priority queue for tasks. To efficiently organize tasks by priority, you need to build a heap from an unordered list of task priorities.

🎯 Goal: Build a max heap from an array of integers using the heapify process. You will write code to create the array, set up the heap size, implement the heapify function, and then build the heap by applying heapify to the array.

📋 What You'll Learn

Create an array called arr with the exact values: {4, 10, 3, 5, 1}

Create an integer variable n to store the size of the array

Write a function heapify that takes the array, size n, and an index i to maintain the max heap property

Use a loop to build the heap by calling heapify from the last non-leaf node up to the root

Print the array after building the heap to show the max heap structure

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and efficient sorting algorithms like heapsort.

💼 Career

Understanding heap construction is important for software engineers working on performance-critical applications and systems programming.

1

Create the array and size variable

Create an integer array called arr with the values {4, 10, 3, 5, 1} and an integer variable n that stores the size of arr.

DSA C++

// Create the array arr with values {4, 10, 3, 5, 1}
// Create the integer n to store the size of arr
// Your code here

Hint

Use int arr[] = {4, 10, 3, 5, 1}; to create the array and int n = sizeof(arr) / sizeof(arr[0]); to get its size.

2

Write the heapify function

Write a function called heapify that takes three parameters: an integer array arr, an integer n for the size of the heap, and an integer i for the index to heapify. The function should maintain the max heap property by comparing the node at i with its children and swapping if needed.

DSA C++

#include 
using namespace std;

void heapify(int arr[], int n, int i) {
    // Your code here
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    return 0;
}

Hint

Use the formulas left = 2 * i + 1 and right = 2 * i + 2 to find children. Compare and swap if needed, then call heapify recursively.

3

Build the heap using heapify

Use a for loop with an integer i starting from n / 2 - 1 down to 0. Inside the loop, call heapify(arr, n, i) to build the max heap from the array.

DSA C++

#include 
using namespace std;

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

    if (left  arr[largest]) {
        largest = left;
    }

    if (right  arr[largest]) {
        largest = right;
    }

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

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Use a for loop to build the heap
    // Your code here

    return 0;
}

Hint

Start from the last parent node at n / 2 - 1 and move up to the root at 0, calling heapify each time.

4

Print the array after building the heap

Use a for loop with an integer i from 0 to n - 1. Inside the loop, print each element of arr followed by a space. After the loop, print a newline.

DSA C++

#include 
using namespace std;

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

    if (left  arr[largest]) {
        largest = left;
    }

    if (right  arr[largest]) {
        largest = right;
    }

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

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Print the array elements after building the heap
    // Your code here

    return 0;
}

Hint

Use a for loop to print each element followed by a space, then print a newline.

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