Time complexity of building a heap

As we know the [Heap data structure](https://www.prepbytes.com/blog/heap/applications-of-heap-data-structures/ “Heap data structure”) fulfills two properties, the first is of complete binary tree and the second is a heap order property.

  1. The complete binary tree has all levels filled except the last level and all nodes of the last level should be aligned from left to right.

Example of perfect Complete Binary Tree:-

  1. The heart of heap data structure is the Heapify algorithm, which is used to maintain the second property of heap data structure i.e Heap order property. According to the heap order property in the min-heap, every node’s value must be smaller than its children and in the max-heap, every node’s value must be greater than its children.

For example:

a max heap

Time complexity analysis of building a heap:-

After every insertion, the Heapify algorithm is used to maintain the properties of the heap data structure. So, we will first discuss the time complexity of the Heapify algorithm.

For example:

Pseudo Code

max_Heapify(A, i){ 
left_child = 2*i; 
right_child = 2*i +1; 
if(left_child <= A.heap_size() and A[left_child] > A[i]) 
       largest = l; 
else largest = i; 

if(right_child <= A.heap_size() and A[right_child] > A[largest])  
        largest = r; 

if(largest != i) 
        swap(A[largest],A[i]) 
        max_Heapify(A,largest) 
} 

build_Max_Heap(A){ 
A.heap_size ← A.length 
for i ← A.length/2 downto 1 
         max_Heapify(A, i) 
} 

From the above example, we can conclude that the Heapify algorithm’s time complexity is equal to O(height of the complete binary tree) i.e O(log N).

Trivial Analysis:

Each call to MAX-HEAPIFY requires log(n) time, we make n such calls O(nlogn)

Tighter Bound:

Each call to MAX-HEAPIFY requires time O(h) where h is the height of node i. Therefore running time is

This article tried to discuss Time complexity of building a heap. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *