C Program: Implementing and testing Heapify function

Last update on December 20 2024 13:05:28 (UTC/GMT +8 hours)

Write a C program that implements a function to heapify a given node in a heap. Check the function with different positions in the heap.

Sample Solution:

C Code:

#include <stdio.h>

// Function to heapify a subtree rooted with node i which is an index in arr[]
void heapify(int arr[], int n, int i) {
    int largest = i;  // Initialize largest as root
    int left = 2 * i + 1;  // left child
    int right = 2 * i + 2; // right child

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        // Swap the found largest element with the root
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    // Test array
    int array[] = {14, 10, 18, 7, 5};
    int n = sizeof(array) / sizeof(array[0]);

    printf("Original Array: ");
    printArray(array, n);

    // Test heapify function with different positions in the heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        printf("Heapify at position %d: ", i);
        heapify(array, n, i);
        printArray(array, n);
    }

    return 0;
}

Output:

Original Array: 14 10 18 7 5
Heapify at position 1: 14 10 18 7 5
Heapify at position 0: 18 10 14 7 5

Explanation:

In the exercise above,

heapify: This function takes an array, its size, and an index as input and ensures that the subtree rooted at that index maintains the max-heap property. It compares the node with its left and right children, swaps with the larger child if necessary, and recursively calls itself on the affected sub-tree.
printArray: This function prints the elements of an array.
In the main function:

It initializes an array.
Prints the original array.
Test the heapify function with different positions in the heap, printing the array after each heapification process.

Flowchart:

C Programming Code Editor:

Previous: Implementing Heap sort with max Heap.
Next: Priority Queue using max Heap - Enqueue and Dequeue operations.