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

Build Heap from Array using Heapify

📖 Scenario: You are working with a list of numbers that you want to organize into a special tree structure called a heap. This heap helps you quickly find the largest number.Imagine you have a messy pile of books and you want to arrange them so the biggest book is always on top. This project will help you do that with numbers using a method called heapify.

🎯 Goal: You will write a program in C that takes an array of numbers and rearranges it into a max heap using the heapify process.At the end, you will print the array showing the heap order.

📋 What You'll Learn

Create an array with exact numbers

Create a variable for the size of the array

Write a function to heapify a subtree

Write a function to build the heap from the array

Print the final heap array

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding heap construction is important for software engineers working on efficient data processing, real-time systems, and algorithm optimization.

1

Create the array and its size

Create an integer array called arr with these exact values: 4, 10, 3, 5, 1. Also create an integer variable called n and set it to the size of the array, which is 5.

DSA C

# Create the array arr and the variable n for its size
# Your code here

Hint

Use int arr[] = {4, 10, 3, 5, 1}; to create the array and int n = 5; for the 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, and an integer i for the index to heapify. This function should rearrange the subtree rooted at i to satisfy the max heap property.

DSA C

int arr[] = {4, 10, 3, 5, 1};
int n = 5;

// Write the heapify function below
// Your code here

Hint

Use the formula left = 2 * i + 1 and right = 2 * i + 2 to find children. Swap if child is bigger and call heapify again.

3

Write the buildHeap function

Write a function called buildHeap that takes the integer array arr and its size n. Use a for loop with variable i starting from n / 2 - 1 down to 0 to call heapify(arr, n, i) for each i.

DSA C

int arr[] = {4, 10, 3, 5, 1};
int n = 5;

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

// Write the buildHeap function below
// Your code here

Hint

Start from the last parent node at n / 2 - 1 and call heapify for each node up to the root.

4

Build the heap and print the array

Call the function buildHeap(arr, n) to build the heap. Then use a for loop with variable i from 0 to n - 1 to print each element of arr followed by a space. Finally, print a newline.

DSA C

int arr[] = {4, 10, 3, 5, 1};
int n = 5;

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) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

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

// Build the heap and print the array
// Your code here

Hint

Call buildHeap(arr, n) first. Then print the array elements separated by spaces.

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 reverse the array elements

D. To rearrange the array elements to satisfy the heap property

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 the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min 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, n, i);

C. heapify(n, arr, i);

D. heapify(arr, i, n);

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

   Calling heapify(arr, n, i); matches the standard parameter order: array, size, index.

3. Final Answer:

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

4. Quick Check:

   Function call order = arr, size, index [OK]

Hint: Remember: array first, then size, then index [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, 1) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify children of index 1

   Index 1 has children at indices 3 and 4 with values 5 and 1.

2. Step 2: Compare and swap if needed

   Value at index 1 is 10, which is greater than both children, so no swap needed.

3. Final Answer:

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

4. Quick Check:

   Parent >= children, no change [OK]

Hint: Check parent vs children, swap only if smaller [OK]

Common Mistakes:

• Swapping when parent is already largest
• Mixing up child indices
• Assuming heapify sorts entire array

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. Loop should start from n/2 - 1 and go down to 0

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

C. heapify function parameters are incorrect

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building starts from last non-leaf node at index n/2 - 1 down to 0.

2. Step 2: Check loop direction and range

   Loop incorrectly goes up from 0 to n/2, should go down from n/2 - 1 to 0.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without going down
• Incorrect heapify parameters

5. You have the array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify from the bottom up, what is the final array?

hard

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

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

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

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

Solution

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

   Last non-leaf node index = n/2 - 1 = 2. Heapify at index 2: children 5 and no right child. Swap 2 and 5 -> [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 swap -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Largest is 9 at index 1, swap -> [9,3,5,1,4,2]. Heapify at index 1 again: 3 with children 1 and 4, largest is 4 at index 4, swap -> [9,4,5,1,3,2]

4. Final Answer:

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

5. Quick Check:

   Bottom-up heapify fixes subtree order [OK]

Hint: Heapify bottom-up swaps parents with largest child [OK]

Common Mistakes:

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