GATE CSE 2003 | Question: 63, ISRO2009-25

Question

A data structure is required for storing a set of integers such that each of the following operations can be done in $O(\log n)$ time, where $n$ is the number of elements in the set.

1. Deletion of the smallest element

2. Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

• A. A heap can be used but not a balanced binary search tree

• B. A balanced binary search tree can be used but not a heap

• C. Both balanced binary search tree and heap can be used

• D. Neither balanced search tree nor heap can be used

Comments

heap will give you minimum in O(logn) but it will take O(n) time for build heap after deleting the minimum and fixing the heap property and almost completeness of the Heap.

But AVL tree in any case, will give you log(n) time complexity

---

shashank bro you are wrong, deletin will take logn tie because we swp last element with first element if it is min heap ad then apply min heapify- total logn time. Since they have not spefied min or ma we can use any and we do get loogn for min heap, but woud get n for max hep..

---

here Avl tree also possible ryt ? , correct & Tag me if i'm wrong

Answer 1

Balanced search tree have height $\log n$

Deletion of smallest element will take $O(\log n)$ time

Finding a element is present/not and doing insertion: $O(\log n)$

Heap(MIN) is also an almost complete binary tree have height $\log n$

Deletion of smallest element will take $O(\log n)$  time (root element removal, replace with last element +balancing)

Finding a element is present/not and insertion: Finding only takes  $O(n)$, insertion then balancing take $O(\log n)$. So, total $O(n)+O(\log n)=O(n).$

Answer is B.

(even if its maxheap our ans does not change only time for deletion of min will increase $O(n)$)

Comments

What if tree becomes unbalanced after Insertion. By balanced tree they mean height balanced or weight balanced? Bcoz Complexity to balance the tree again after Insertion Might Vary!

---

The only thing to notice here is that searching an element in Heap is O(N). That’s why Insertion of an element if it is not already present in the set takes O(N).

Reference: algorithm - Search an element in a heap - Stack Overflow

---

Insertion of element in the heap will take  $O (logn)$ if we already know that the element which we want to insert is NOT present in the set (heap)  because we don't  need to search in this case and searching the element takes $O (n)$ 

Answer 2

Insertion of an element if it is not already present in the set

Means first search, then insert if needed.

---

Balanced Binary Search Tree:

1. Deletion of the smallest element: $O(logn)$
2. Search: $O(logn)$
3. insert: $O(logn)$

It qualifies.

 

Heap

1. Deletion of the smallest element: $O(logn)$
2. Search: $O(n)$
3. Insert: $O(logn)$

It doesn't qualify.

Option B

---

 

Reasons for the time complexities:-

Balanced Binary Search Tree:

1. The smallest element will ALWAYS be the last left child of the root. ie, the leftmost leaf. Height of a balanced BST is $O(logn)$ hence to reach the node with the smallest value, we need $O(logn)$ time.
2. To search an element, at any point we'll have only one path to go. The length of the path = height of the tree = $O(logn)$.
3. To insert an element, we first need to find its right place in the BBST. Again, same as above. $O(logn)$

 

Heap

1. If we employ a min heap, the smallest element is the root node. To delete the root, first switch the last indexed element and the root. Then delete the last indexed element (which is the former root) Then call heapify. So, $O(logn)$
2. A random value in a heap could be anywhere. All we know is that the nth largest value in a max-heap would be in the first n levels. Even that's not enough information.
   Could be anywhere, so go through all the elements, hence $O(n)$
3. To insert, insert after the current-last index; then call heapify. So, $O(logn)$

Comments

What if tree becomes unbalanced after Insertion. By balanced tree they mean height balanced or weight balanced? Bcoz Complexity to balance the tree again after Insertion Might Vary!

---

@Amcodes What if tree becomes unbalanced after Insertion

If you insert one element in a balanced binary search tree, height will remain O(logn).

---

Amcodes

some operations are performed after each and every insertion to keep the tree balanced!

---

Great Answer

Answer 3

option B

balanced binary search tree

to find if the element is present it takes O(log n)

then if not just insert it takes O(log n).

deleting an element takes O(log n) ,so balanced BST is one of our viable data structure now lets move on to heap

 

they have not made a sound whether its max heap or min heap so lets be general ..

finding an element if its already present it takes O(n)

suppose the element we are searching for is at the lowest level . then we  compare our element with root and find out thats its not that element we are searching for ,then we are standing at cross roads whether to go the left subtree or right subtree .so we need to go to both of the subtrees as we dont have clues to which subtree which belongs ..

so no need to go further just declare balanced BST is the only possible data structure we are in need of .........

Comments

I knw answer is b..

But my doubt is what will be the complexity of deletion of smallest element in a balanced binary search tree?

O(lg n)  or O(1)..?

I think it can be done in O(1)..

AS WE just need to find the leftmost elment as it will be smallest..

---

what will be the complexity of deletion of smallest element in a balanced binary search tree?

It will be O(logn) because we don’t know how much left we need to go.

we may find it just left to root node or maybe left of left of left of …. root node.

Answer 4

Its not specified whether the heap is min or max . If min heap then after deleting we need to adjust the tree hence takes logn bt incase it's max heap no need to take adjustment as min element is on the leaves level , it's then O(1).

option C

Comments

Yes. You are correct. But not just the "max element" cause problem. All the elements in the last level can cause this problem. So, only binary search tree is the answer here.

---

Sir, no doubt regarding O(n) time for finding smallest element in Max Heap but how do we implement it using program? Please help with explanation, program not needed. Thank you.

---

Heap is not possible because for insertion we need to check element is present or not so it will take O(n) time