Min Heap

Question

In a min-heap, the next largest element of a particular element can be found in ___ time.

A) O(1)

B) O(log n)

C) O(n)

Comments

O(n)?

---

O(n) is the time complexity when just give you an arbitrary element and asks you to find its successor.

But if I tell you about the position of a node(you have the key) and ask you next largest element(successor of key) then it should be node with smaller key among the children of that node. O(1)

Am I correct?

---

how can you find in-order successor of a key in O(1) in min-heap?

Answer 1

The key thing to notice here is : we are using binary heap instead of BST as the concerned data structure .

And we know :

The only requirement in binary heap is that the tree should be almost complete binary tree and parent value should be less than both left and right children values. However there is no relation left and right children as in the case of BST we have ..Thus ordering among the same level nodes dont matter here as long as the min heap property is satisfied w.r.t. their parent nodes.

So say we are considering the leaf nodes of a tree of height 3. So we can have 8 nodes in leaf level.And let all leaf nodes are occupied ..Let the key values be distributed such that we have key values : [8 - 15] in the leaf level..

So now wht can happen in worst case is that 8 is in the left most extreme and  9 in the rightmost extreme as we can have such valid minheap.The node having 8 can be in the next to rightmost extreme and 9 in the rightmost extreme . So any permutation amongst the key values of a level in the tree is possible given that keys for a specific level has been specified to form minheap.

Thus in worst case we may end up searching all elements in the level . In last level we have (n/2) nodes maximum . So maximum of (n/2 - 1) nodes are to be compared for next maximum.

Hence O(n) should be required complexity.

Comments

@Habibkhan You are born to be a great Teacher. Again Great Explanation. Thanks bro

---

@Habibkhan If pointer is given to that particular element than we just need to search the entire next level but if only key is given then we have to first find that element(in worst case the entire min heap) then compare it with elements in same level or to all ements in next level(if all are smaller in same level). Now also O(n)

---

@Shivam

think of this scenario, i am showing partially filled min heap

2 3 1000............. // dots represent there are many more elements

now you can see that if you have to find next greatest of 1000, you have to search entire subtree rooted at '3'...which will take O(n) time, so no matter if you already have pointer to '1000' or not, it will take O(n) time in orst case..

---

@joshi_nitish Thanks bro. Got your idea. We have to search entire tree.

Answer 2

In heap we can do it by built heap method i.e. O(n).

• Now, as it is a particular element, I think pointer is not given, in that case search the whole tree take O(n).
• When node is found find it's parent or we can say it's root, in in O(1) time by index.  Suppose node is x[i], then finding root will be

• if(i%2==0) parent=x[i/2];
  else parent=x[(i-1)/2];

• When root is found, delete root and apply heapify with build heap precedure O(n)
• Compare root with left child and right child in O(1) time
• Among left and right child , which one is minimum will be the ans(As it is a min heap)

Here complexity O(n)+O(n)=O(n)

Comments

@srestha

your method will not yeild correct answer,

consider a min-heap -> 4 9 8 15 16 11 13, now

find next greatest of 8, your method will give 11, but actually it will be 9.

---

@ joshi_nitish

thanks

yes edited

Now chk if anything missing