The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
41 views

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

 

 

asked in Programming by Boss (13.8k points) | 41 views

1 Answer

+2 votes

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))$

answered by Active (1.1k points)
+1

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)

Related questions

+2 votes
0 answers
1
asked Jan 24, 2018 in Programming by VS Loyal (9.9k points) | 105 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,004 questions
51,323 answers
177,494 comments
66,668 users