Being the most popular programming language in the world, C programming is learned by students across the globe. It has many versatile concepts where students get stuck due to a lack of understanding of the subject knowledge and they look for C Programming help. So, today we are going to discuss a very common question asked by students on the Internet. Welcome to CodingZap’s new blog “How to build max heap from an array using C”.
Let us first discuss Heap and its properties first then we would jump into building max heap from an array in C programming.
What is Heap?
A heap is a special tree data structure that satisfies heap property. In this implementation, I am using a binary tree for simplicity.
How to represent a binary tree as an array
- Root is at index 0 in the array.
- Left child of i-th node is at (2*i + 1)th index.
- Right child of i-th node is at (2*i + 2)th index.
- The parent of the i-th node is at (i-1)/2 index.
What are the Properties of Heap?
A heap can be of two types based on either of two heap properties –
Max Heap
A max-heap is a heap in which the value of each node is greater than or equal to the values of its children.
Min-Heap
A min-heap is a heap in which the value of each node is less than or equal to the values of its children
What is Heapify?
Heapify is the basic building block of the algorithm of creating a heap data structure from a binary tree.
Heapify goes through a top-down approach and makes every subtree satisfy the max heap starting from the given node.
PseudoCode of Heap :
indexOfNode is the root of a subtree
Heapify(array , sizeOfArray , indexOfNode)
Largest = findMaximum of ( indexOfNode , leftChild , rightChild )
If Largest != indexOfNode i.e the root
Swap ( Largest with indexOfNode )
Heapify( array , sizeOfArray , Largest )
Build Max Heap: The Process for Building Max Heap
If we start making subtree heaps from down to the bottom, eventually the whole tree will become a heap.
The Build Heap function will loop starting from the last non-leaf node to the root node, and call the Heapify function on each. So that each node satisfies the max heap property. Similarly implementing stack using a linked list in C programming is easy if you follow the right steps.
Coming to our topic, we are starting from the last non-leaf node because leaves are already heaps.
To find an index of the Last Non-leaf Node,
index of Last Non Leaf Node = (n/2) – 1
where n is the number of nodes in a tree
Supporting Functions
These functions will help with basic utilities for
- Printing an array
- Swapping two variables
Driver Code
In general Driver code is written to test your developed program and in the below screenshot, you can find the driver code. If it’s not written well, it might flag an error in the C programming project.
This will run our code.
Final Code of “How to Build Max Heap from an Array using C”
We have written the final code for building the max heap. You can refer to this code and practice by yourself. Our codes are very well-commented and written as per college standards. However, you can also read our article on Dynamic memory allocation in C programming and learn more about it.
You can run this code to get the correct output shown below:
// Build a Heap from an Array with C
#include <stdio.h>
// swap function
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
// Function to print the Heap as array
// will print as - 'message array[]\n'
void printArray(char message[], int arr[], int n)
{
printf("%s ",message);
for (int i = 0; i < n; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
// To heapify a subtree with node i as root
// Size of heap is n
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int leftChild = 2 * i + 1; // left child = 2*i + 1
int rightChild = 2 * i + 2; // right child = 2*i + 2
// If left child is greater than root
if (leftChild < n && arr[leftChild] > arr[largest])
largest = leftChild;
// If right child is greater than new largest
if (rightChild < n && arr[rightChild] > arr[largest])
largest = rightChild;
// If largest is not the root
if (largest != i)
{
// swap root with the new largest
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected sub-tree i.e, subtree with root as largest
heapify(arr, n, largest);
}
}
// Function to build a Max-Heap from a given array
void buildHeap(int arr[], int n)
{
// Index of last non-leaf node
int lastNonLeafNode = (n / 2) - 1;
// Perform level order traversal in reverse from last non-leaf node to the root node and heapify each node
for (int i = lastNonLeafNode; i >= 0; i--)
{
heapify(arr, n, i);
}
}
// Driver Code
void main()
{
// Array
int arr[] = {4, 18, 17, 10, 19, 20, 14, 8, 3, 12};
// Size of array
int n = sizeof(arr) / sizeof(arr[0]);
printArray("Array is : ", arr, n);
buildHeap(arr, n);
printArray("Array representation of Heap is : ", arr, n);
}
Output
Input Array :
4
/ \
18 17
/ \ / \
10 19 20 14
/\. /
8 3 12
Output Max Heap :
20
/ \
19 17
/ \ / \
10 18 4 14
/\ /
8 3 12
As we can see every node is greater than its child nodes ( max heap property ). Didn’t understand the code? No issues, You can always ask for programming help from experts at CodingZap.
Heap Data Structure Applications:
- Priority queue.
- Dijkstra’s Algorithm
- Heap Sort
So, hope you have liked this piece of article. Share your thoughts in the comments section and let us know if we can improve more. Still, curious about learning C programming then here is the guide to start learning C in 5 easy steps.
