## Priority Queues (Binary Heap)

### 9. Analysis

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?

Previous Chapter: Heapsort

This document was last updated 13.8.2009. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.