The Blog

# How to Build Max Heap from an array using C

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.

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

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 codingzapserver
Content Writer at Codingzap Technology. Writes Informative and tech posts.