Algorithm and data structure closed

Question

https://gateoverflow.in/?qa=blob&qa_blobid=17275535249024428371

Comments

extract first elements thats going to take 0(logn) than than repeat the same till 6 steps

you will get it in O(logn)

---

@manvi_agarwal

add the image in the question, why you just keep the link ?

@arvin

it is a gate question,i hope it is O(1)

---

yes @shaikh yes it should be 0(1).

---

sure! i will take care of this definately

---

guys some are taking out O(1) while some are taking out O(logn)

like in some lectures, we have O(logn) while, Kiran kumar pasupuleti sir has given  we have O(1). so whats the orrect explaination

---

it can be solved for 0(1) as well as O(logn) it will depend upon the criteria which is  :

1) O(1) if you can easily access elements of the heap. (comparison will be 2^k-1 where k=constant )

2) O(logn) if you can only access the first element of heap.

i think their answer must be different based on the idea of accessing elements of the heap.

---

it should be O(log n) because

min element will be root takes O(1).

2nd smallest will be at level 1(root is level 0)

3rd smallest element will be at 2nd or 3rd level

 

similarly 7th smallest element can be found in level 1 to level 6

now we can not do traversal in min-heap or max-heap so first have to delete smallest element then only 2nd smallest element can be found.

after each deletion we have to perform heapify operation which takes O(logn)

so for doing k operation we will require O(k*log n)=O(log n)