## Priority Queues (Binary Heap)

- Introduction
- Array Representation of Binary Heap
- MinHeap vs. MaxHeap
- Insert
- DeleteMax
- Preserving the Heap Order Property
- BuildHeap
- Heapsort
- Analysis

###

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.