Height of a heap is the height of its root. It can be shown that the
height of a heap of size n is ⌊lg n⌋
Example 2: If there are 10 items in a heap (n = 10), the
height of the heap is ⌊lg 10⌋ = ⌊3,32...⌋ =
3.
Complexity of MAX-HEAPIFY in the worst case is when the MAX-HEAPIFY function is called once on each level of the heap.
There are h + 1 = ⌊lg n⌋ + 1 levels in the heap.
From this it follows that the time complexity of the algorithms is
T(n) = O(lg n).
Complexity of insert and deleteMin/Max operations
Since the deleteMin/Max operation uses the HEAPIFY algorithm, the time
complexity of deleteMin/Max is also O(lg n).
Exercises: Analysis
a) Analyse the worst case time complexity of insertion of a single item.
b) Deduce what is the time complexity of building a heap using single insertions (N items are added to the heap, one at a time).
a) What is the worst case time complexity of Heapsort?
This document was last updated 13.8.2009. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.