Build Heap is a process of building a Heap from a given element generally in an array format. The resulting heap will be either max-heap or a min-heap.
The most important function in converting an array into Binary heap is Heapify function.
Heapify
Heapify is used to convert a Binary tree to a heap data structure. Heapify procedure when applied to a node arranges the node and its subtree(children) in such a way that they follow Heap property.
The following example shows on applying the Heapify on node 9, it converts the tree into a valid heap.
9 27 / \ Max-heapify(9) / \ 27 25 =========> 18 25 / \ / \ / \ / \ 18 11 16 24 9 11 16 24 (Not Max-Heap) (vaild Max-Heap)
Algorithm
- Let the current node be i, start by finding the left and right child of the current node. left-child = heap[2*i] and right-child = heap[2*i + 1] and assign a variable largest with the index i, of current node.
- If left-child exists and is less than the current node, take assign the variable largest the index of left-child.
- Else if the right-child exists and is less than the current node, take assign the variable largest the index of right-child.
- If largest != i swap the values at the index i and the index largest i.e. swap(heap[i], swap[largest]), and again call the Max-Heapify procedure with largest as the new index and repeat the step 1.
- Else Stop. The tree is now following Max-Heap property.
The time complexity of performing Max/Min Heapify is O(log N)
max_heapify(arr , i)
{
largest = i
left-child = arr[2*i]
right-child = arr[2*i + 1]
if (left-child < arr.size) && (arr[left-child] > arr[largest])
largest = left-child
else if(right-child < arr.size) && (arr[right-child] > arr[largest])
largest = right-child
if(largest != i)
swap(arr[largest] , arr[i])
max_heapify(arr, largest)
}Let’s understand how Heapify works with the following example.
9 / \ 27 25 / \ / \ 18 11 16 24 Use Heapify to convert above tree into a Max-Heap Max-Heapify(9) step 1: 9 < 27, hence swap 9 & 27, also since swapping has happend call heapify again 27 / \ 9 25 / \ / \ 18 11 16 24 step 2: 9 < 18, hence swap 9 & 18, also since swapping has happend call heapify again 27 / \ 18 25 / \ / \ 9 11 16 24 step 3: 9 doesn't have any left child so stop. 27 / \ 18 25 / \ / \ 9 11 16 24 This is a Max-Heap
Build Heap
As explained above, the Heapify function when applied to a node arranges the node and all of its subtree only to follow heap property. But if we apply the Heapify function to every node(except the child nodes, since child nodes always follow the heap property), then the entire tree will follow the heap property.
This is how the build heap function works. The build heap, call Heapify function of every node of the tree, from the last level to the first level iteratively and the resulting binary tree follows heap property.
Algorithm
The last non-leaf node in Heap with n elements will be –
- floor(n/2) will be the last non-leaf node if an array is starting from 1 and elements are in the range [1 to n]
- floor(n/2)-1 will be the last non-leaf node if an array is starting from 0 and elements are in the range [0 to n-1]
Build-heap(arr, n)
{
//you can start with the last element of array but as discussed
// the node floor(size/2) is the last non-leaf node
last_parent = floor(n/2);
for(i= last_parent; i>=0; i--)
max_heapify(arr, i);
}Let’s understand how to build a Max Heap with the following Binary tree given in array representation-
Array representation = [2, 4, 15, 6, 18, 12, 10, 9, 8, 23, 27]
Corresponding Binary Tree -
2
/ \
4 15
/ \ / \
6 18 12 10
/ \ / \
9 8 23 27
Convert the above Binary Tree into Max Heap
Build Heap - The Build Heap function will work by calling Heapify
function on nodes [18, 6, 15, 4 , 2] in same order.
1. Heapify 18
2
/ \
4 15
/ \ / \
6 27 12 10
/ \ / \
9 8 23 18
2. Heapify 6
2
/ \
4 15
/ \ / \
9 27 12 10
/ \ / \
6 8 23 18
3. Heapify 15
2
/ \
4 15
/ \ / \
9 27 12 10
/ \ / \
6 8 23 18
4. Heapify 4
2
/ \
27 15
/ \ / \
9 23 12 10
/ \ / \
6 8 4 18
5. Heapify 2
27
/ \
23 15
/ \ / \
9 18 12 10
/ \ / \
6 8 4 2
The following tree is now following the property of Max Heap
The arrary representation of above Heap -
[27, 23, 15, 9, 18, 12, 10, 6, 8, 4, 2]
Implementation of Max-Heapify & Build Heap in CPP
#include <bits/stdc++.h>
using namespace std;
int heapify(int arr[], int i, int n)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, largest, n);
}
return 0;
}
int buildHeap(int arr[], int n)
{
int last_parent = (n / 2) - 1;
for (int i = last_parent; i >= 0; i--) {
heapify(arr, i, n);
}
return 0;
}
int main()
{
int arr[] = { 2, 4, 15, 6, 18, 12, 10, 9, 8 ,23, 27 };
int n = sizeof(arr) / sizeof(arr[0]);
buildHeap(arr, n);
cout<<"Array representation of Max Heap -"<<endl;
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout <<endl;
return 0;
}
Time Complexity
The time complexity of running Heapify operation is O(log N) where N is the total number of Nodes. Since the Build Heap function works by calling the Heapify function O(N/2) times you might think the time complexity of running Build Heap might be O(N*logN) i.e. doing N/2 times O(logN) work, but this assumption is incorrect.
The actual time complexity of Build Heap function is O(N*logN)