How to build a max heap using an array

A heap is a binary tree that meets the heap property. Heap can be of two types:

Min heap: The value of each node is larger than or equal to the value of its parent. The node with the lowest value is the root.
Max heap: Each node's value is smaller than its parent's value. The highest value element is at the root.

Building a heap from an array ensures that the heap order property is maintained after every input. For max heap, the newly entered value is checked whether it is smaller than its parent. If it's not, it is swapped.

How to represent a binary tree as an array

The root is at index 0 in the array.
The left child of the ith node is at ( $2*i + 1$ )^th index.
The right child of the ith node is at ( $2*i + 2$ )^th index.
The parent of the ith node is at $(i-1)/2$ ^th index.

Let's take a look at an example. Consider the following max heap:


#include <iostream> 
using namespace std;
int size; // size of array 
void heapify(int array[], int i) 
{ 
	int large = i; // The node which will be heapified 
	int left = (2 * i) + 1; // left child node 
	int right = (2 * i) + 2; // right child node 
	// Check if left child is larger 
	if (left < size && array[left] > array[large]) 
		large = left; 
	// Check if right child is larger 
	if (right < size && array[right] > array[large]) 
		large = right; 
	// If largest is not parent 
	if (large != i) { 
		swap(array[i], array[large]); 
		
		// Recursively changed sub-tree 
		heapify(array, large); 
	} 
} 
void build_heap(int array[]) 
{
	// heapify each node of array 
	for (int i = size; i >= 0; i--) { 
		heapify(array, i); 
	} 
} 
// Driver Code 
int main() 
{ 
	
	int array[] = { 1, 5, 6, 8, 9, 7, 3}; 
	size = sizeof(array) / sizeof(array[0]); //size
	cout << "Sample Array : "; 
	for (int i = 0; i < size; ++i) //loop for printing array 
		cout << array[i] << " ";
	cout <<endl; 
	//calling heap function
	build_heap(array); 
  	cout << "Heapify Array: ";
	for (int i = 0; i < size; ++i) //loop for printing heap
		cout << array[i] << " ";
	return 0; 
}

Explanation

Line 5–11: We define a size variable and a heapify() function. We declare the large, left , and right variables to keep track of nodes.
Line 14–19: We check the given value whether it is greater than the left and right child.
Line 22–26: If a parent is not the largest, the values are swapped, and the affected subtree is again called in the heapify() function.
Line 30–36: Each value is called in the heapify() function using a for loop.

Time Complexity

It takes $O(logn)$ time and complexity to heapify one node. Therefore, the time complexity for building a heap from an array is $O(n*logn)$ , where n is the total number of elements in an array. The space complexity for this approach is $O(1)$ .

How to build a max heap using an array

How to represent a binary tree as an array

Build max heap from the array

Example

Explanation

Time Complexity