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.