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+12*i + 1)th index.

  • The right child of the ith node is at (2∗i+22*i + 2)th index.

  • The parent of the ith node is at (i−1)/2(i-1)/2th index.

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

%0 node_1 9 node_2 8 node_1->node_2 node_3 7 node_1->node_3 node_1658064506720 1 node_2->node_1658064506720 node_1658064502420 5 node_2->node_1658064502420 node_1658064536669 6 node_3->node_1658064536669 node_1658064559127 3 node_3->node_1658064559127
Max Heap

The array representation of the max heap above is as follows:

%0 node_1 9 node_2 8 node_3 7 node_1658064192862 1 node_1658064260898 5 node_1658064277143 6 node_1658064283389 3
Max Heap- Array

Build max heap from the array

Let's see how we build max heap from a given array. Here we consider a random array. First, we create a binary tree of the array. Then, starting from the leaf nodes, we swap the nodes based on their values.

The technique transfers the smallest node to the leaf nodes and the largest node towards the root. The values are swapped until the element of each node is less than the element at its parent. Let's visualize it:

1 of 12

Example

Here's the step-by-step implementation of building a heap from a given array:

#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)O(logn)time and complexity to heapify one node. Therefore, the time complexity for building a heap from an array is O(n∗logn)O(n*logn), where n is the total number of elements in an array. The space complexity for this approach is O(1)O(1).

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved