Heap sort Complexity. Time complexity shows growth in time requirement, but not exact time. Time complexity to sort element in heap is O(nlogn). To understand, that how this figures are made for this complexity, let us have a look on some complexity for inserting and deleting in heap. You can also refer Heap sort : How Heap sort is implemented.
Heap sort Complexity:
a). To insert a single node in an empty heap is : O(1).
b). To insert a single element in a n node heap is : O(logn). Let us first understand this that how O(logn) comes. Let here be at-most ‘N’ number of comparison is done for inserting an element in heap. This number are equal to depth of tree, so the depth of tree will be equal to the time complexity of heap for insertion of an element which consist of n element. If n nodes are inserted than depth of tree will be :
depth 0 have : 2^0 elements,
depth 1 have : 2^1 elements,
depth 2 have : 2^2 elements,
…. . …. . ……….
in similar way
depth d have : 2^d elements.
so Total number of elements inserted in dth row be n.
This gives n = 2^0 + 2^1 + 2^2 + 2^3……………+ 2^d.
This forms GP, and get the expression by GP sum formula as n+1=2^(d+1).
This equation then converted in the form of d as d=log(n+1)-1. So for very large value of n, 1 can be neglected, this gives
and d=time complexity for inserting one elemnet=O(logn).
c.) To insert n elements in a n node heap is : O(nlogn).
d.) To delete the largest element in a max heap tree : O(1).
e.) To delete the smallest element in a max heap tree : O(logn).
f.) To delete n elements in a max heap tree : O(nlogn).
g.) To create a heap, time complexity will be : O(nlogn).
Now to sort the heap tree requires,
1. arrange or insert the elements in a form of heap i.e O(nlogn) and
2. delete the elements one by one after swapping operation O(nlogn)
This gives Heap sort complexity = O(nlogn) + O(nlogn).
= 2 O(nlogn) = O(nlogn).
Have a look on c program for heap sort click. I hope the above article explained you heap sort complexity in brief. If you are having any problem or suggestion related to heap complexity, then do comment below.