practice questions

Question

the time required to find 7th smallest element in min heap of size n vertices? solve and plz explain how?

Answer 1

It takes O$\left ( 1 \right )$ Time since 7th element present at atmost 7th level so only we need to compare $2^7 -1$ element which is constant in comparision to n.

Comments

@Anirudh. there is no gaurantee that you will find any other element except greatest(in max heap) and smallest(in min heap).

I hope you have clear idea of heap ie how it is created, how it maintained etc. Still if you think that you can find the 7th smallest number in O(1) time, then please remind one thing 7th smallest element can be at 0th level as in case of worst case.

remeber one thing, in heap it not guarantee that right child is always smaller and left one is greater than root.... in this case tree is not heap.....

if you still think you have answered right then its my request to you please justify your answers with example.

Answer 2

Min Heap is faster for searching/deletion of minimum element only.
Searching of 7th smallest element we have to A) delete minimum element which is present at the top of tree and 2)heapify the tree.
repeat steps A and B for 5 more times and then 7th minimum element is found. so the time complexity will be O(log n).

Explaination:
for deletion of 1st minimum node ie root= O(1) and for heapification (find 2nd smallest element) time complexity is O(log n). similary delete and heapifaction will continue till 6th element and after heapication 7th smallest element can be found.

6[O(1) + O(log n)] + O(1) = O(log n)

Comments

@Brijesh. We want upper bound on finding the 7th smallest element. So, BFS should suffice. No question of BST here.

---

@Sushant. you are right it can be done in O(1) but in only one case ie when duplication is not allowed which is optimal case for this question.

If Min-Heap is allowed to have duplicates, then time complexity becomes O(Log n). Also, if Min-Heap doesn't allow directly accessing elements below root and supports only extract-min() operation, then also time complexity becomes O(Log n).

By the way, I am not saying that are wrong, as the its BIg O notation we have to think for wrost case also and that is we do to find out any time complexity.

By the way, this question was previosuly asked in GATE as well and you get O(1) answers over lots of places as well but my friends please take other two conditions into consideration. I hope I am able to put my point.

---

@Brijesh. Too many assumptions complicate the matters and this is my personal experience during the GATE exam. Assume minimum and only which is required by the question or which is necessary to support the statements/arguments in the question.

So, just a thumb rule. Assume nothing as far as possible :)