HEAP (MAX/MIN HEAP)

Question

what is the time complexity of various problems such as:

1) Creating the heap

2) Getting maximum element in the max heap

3) Getting minimum element in the max heap

4) Getting maximum element in min heap

5) Getting minimum element in min heap

6) Heapify the element

7)Build heap

8) Deletion of an element in min heap

9) Deletion of an element in the max heap

10) Insertion of an element in the max heap

11) Insertion of an element in min heap

 

 

Answer 1

1) Creating the heap   - $O(n)$

2) Getting maximum element in the max heap    -  $O(1)$

3) Getting minimum element in the max heap     -  $O(n)$ as the minimum element will be in last level

4) Getting maximum element in min heap     -  $O(n)$ as the maximum element will be in last level

5) Getting minimum element in min heap  - $O(1)$

6) Heapify the element - $O(log(n))$

7)Build heap -  $O(n)$

8) Deletion of an element in min heap - $O(log(n))$ for maintaining min heap property after deletion.

9) Deletion of an element in the max heap - $O(log(n))$

10) Insertion of an element in the max heap - insertion take $O(1)$ but $O(log(n))$ for maintaining max heap property after insertion.

11) Insertion of an element in min heap  - $O(log(n))$

Comments

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n). but if you don't know it's location then Deletion will take O(n)