The Blog

# How to Build Max Heap from an array using C

Welcome to CodingZap’s new blog “How to build max heap from an array using C”. You might have come across this topic and must be wondering:

### 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 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

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.

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 in basic utilities for

• Printing an array
• Swapping two variables Driver Code

This will run our code. ## Final Code of “How to Build Max Heap from an array using C”

`// Build a Heap from an Array with C#include <stdio.h>// swap functionvoid 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 nvoid heapify(int arr[], int n, int i){int largest = i; // Initialize largest as rootint leftChild = 2 * i + 1; // left child = 2*i + 1int rightChild = 2 * i + 2; // right child = 2*i + 2// If left child is greater than rootif (leftChild < n && arr[leftChild] > arr[largest])largest = leftChild;// If right child is greater than new largestif (rightChild < n && arr[rightChild] > arr[largest])largest = rightChild;// If largest is not the rootif (largest != i){// swap root with the new largestswap(&arr[i], &arr[largest]);// Recursively heapify the affected sub-tree i.e, subtree with root as largestheapify(arr, n, largest);}}// Function to build a Max-Heap from a given arrayvoid buildHeap(int arr[], int n){// Index of last non-leaf nodeint lastNonLeafNode = (n / 2) - 1;// Perform level order traversal in reverse from last non-leaf node to the root node and heapify each nodefor (int i = lastNonLeafNode; i >= 0; i--){heapify(arr, n, i);}}// Driver Codevoid main(){// Arrayint arr[] = {4, 18, 17, 10, 19, 20, 14, 8, 3, 12};// Size of arrayint n = sizeof(arr) / sizeof(arr);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 )

## 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.

Also, if you are looking for C Programming Help or C++ Homework Help then hire us for the best services. We have the best expertise in C and C++ Help. Reach us now and get genuine help. codingzapserver
Content Writer at Codingzap Technology. Writes Informative and tech posts.