Time Complexity of building a heap

Last Updated : 17 Jun, 2022

Consider the following algorithm for building a Heap of an input array A.

BUILD-HEAP(A)

heapsize := size(A);

for i := floor(heapsize/2) downto 1

do HEAPIFY(A, i);

end for

END

A quick look over the above algorithm suggests that the running time is $O(n * lg(n))$ since each call to Heapify costs $O(lg(n))$ and Build-Heap makes $O(n)$ such calls.

This upper bound, though correct, is not asymptotically tight.

We can derive a tighter bound by observing that the running time of Heapify depends on the height of the tree ‘h’ (which is equal to lg(n), where n is a number of nodes) and the heights of most sub-trees are small. The height ’h’ increases as we move upwards along the tree. Line-3 of Build-Heap runs a loop from the index of the last internal node (heapsize/2) with height=1, to the index of root(1) with height = lg(n). Hence, Heapify takes a different time for each node, which is:

For finding the Time Complexity of building a heap, we must know the number of nodes having height h. For this we use the fact that, A heap of size n has at most $\left \lceil \frac{n}{2^{h+1}} \right \rceil$ nodes with height h.

a to derive the time complexity, we express the total cost of Build-Heap as-

$T(n) = \sum_{h = 0}^{lg(n)}\left \lceil \frac{n}{2^{h+1}} \right \rceil * O(h)= O(n * \sum_{h = 0}^{lg(n)}\frac{h}{2^{h}})= O(n * \sum_{h = 0}^{\infty}\frac{h}{2^{h}})$

Step 2 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2( $2^{h+1} = 2.2^h$ ). Similarly in Step three, the upper limit of the summation can be increased to infinity since we are using Big-Oh notation. Sum of infinite G.P. (x < 1)

$\sum_{n = 0}^{\infty}{x}^{n} = \frac{1}{1-x}$

On differentiating both sides and multiplying by x, we get

$\sum_{n = 0}^{\infty}n{x}^{n} = \frac{x}{(1-x)^{2}}$

Putting the result obtained in (3) back in our derivation (1), we get

$= O(n * \frac{\frac{1}{2}}{(1 - \frac{1}{2})^2})= O(n * 2)= O(n)$

Hence Proved that the Time complexity for Building a Binary Heap is $O(n)$ .

C

Chirag Manwani

Improve

Previous Article

Applications, Advantages and Disadvantages of Heap

Applications of Heap Data Structure

Similar Reads

Check if a triplet of buildings can be selected such that the third building is taller than the first building and smaller than the second building

Given an array arr[] consisting of N integers, where each array element represents the height of a building situated on the X co-ordinates, the task is to check if it is possible to select 3 buildings, such that the third selected building is taller than the first selected building and shorter than the second selected building. Examples: Input: arr

When building a Heap, is the structure of Heap unique?

What is Heap? A heap is a tree based data structure where the tree is a complete binary tree that maintains the property that either the children of a node are less than itself (max heap) or the children are greater than the node (min heap). Properties of Heap: Structural Property: This property states that it should be A Complete Binary Tree. For

Difference between Binary Heap, Binomial Heap and Fibonacci Heap

Binary Heap:A Binary Heap is a Binary Tree with following properties. It’s a complete binary tree i.e., all levels are completely filled except possibly the last level and the last level has all keys as left as possible. This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min

Time Complexity and Space Complexity

Generally, there is always more than one way to solve a problem in computer science with different algorithms. Therefore, it is highly required to use a method to compare the solutions in order to judge which one is more optimal. The method must be: Independent of the machine and its configuration, on which the algorithm is running on.Shows a direc

Python Code for time Complexity plot of Heap Sort

Prerequisite : HeapSort Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element. We implement Heap Sort here, call it for different sized random lists, meas

Complexity analysis of various operations of Binary Min Heap

A Min Heap is a Complete Binary Tree in which the children nodes have a higher value (lesser priority) than the parent nodes, i.e., any path from the root to the leaf nodes, has an ascending order of elements. In the case of a binary tree, the root is considered to be at height 0, its children nodes are considered to be at height 1, and so on. Each

Building Heap from Array

Given an array of N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap. Examples: Input: arr[] = {4, 10, 3, 5, 1}Output: Corresponding Max-Heap: 10 / \ 5 3 / \4 1 Input: arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}Output: Corresponding Max-Heap: 17 / \ 15 13 / \ / \ 9 6 5 10 / \ / \ 4 8 3

Convert Min Heap to Max Heap

Given an array representation of min Heap, convert it to max Heap. Examples: Input: arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9} 3 / \ 5 9 / \ / \ 6 8 20 10 / \ /12 18 9 Output: arr[] = {20, 18, 10, 12, 9, 9, 3, 5, 6, 8} 20 / \ 18 10 / \ / \ 12 9 9 3 / \ /5 6 8 Input: arr[] = {3, 4, 8, 11, 13}Output: arr[] = {13, 11, 8, 4, 3} Approach: To solve the p

Heap Sort for decreasing order using min heap

Given an array of elements, sort the array in decreasing order using min heap. Examples: Input : arr[] = {5, 3, 10, 1} Output : arr[] = {10, 5, 3, 1} Input : arr[] = {1, 50, 100, 25} Output : arr[] = {100, 50, 25, 1} Prerequisite: Heap sort using min heap. Algorithm : Build a min heap from the input data. At this point, the smallest item is stored

Difference between Min Heap and Max Heap

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Since a heap is a complete binary tree, a heap with N nodes has log N height. It is useful to remove the highest or lowest priority element. It is typically represented as an array. There are two types of Heaps in the data structure. Min-HeapIn a Min-Heap the

Article Tags :

Practice Tags :

Heap