in DS edited by
20,045 views
65 votes
65 votes

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?

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

  3. Both balanced binary search tree and heap can be used

  4. Neither balanced search tree nor heap can be used

in DS edited by
20.0k views

4 Comments

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

I have one doubt in here, insert if it is not already present, does that mean that we have to compare with all elements to check whether it is already present in the heap or not. In Balanced BST it can be done in O(log N) time but it will take O(n) in heap, right? as it is not mentioned that it is min heap or max heap.

0
0
Is worst case time complexity for general insert in heap is O(n) and for min or max heap it is O(logn)?
0
0

As I understand, the part which says

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

require us to traverse all the $n$ elements of the heap, thereby making this insertion a $O(n)$ operation. Otherwise, if it would have been the case of an insertion when the element to be inserted is not present in the heap to start with, it would have taken $O(log \ n)$ time.

Is my understanding right?

3
3
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
1
1

4 Answers

92 votes
92 votes
Best answer

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

edited by

4 Comments

Thanq ,I missed that point
0
0
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!
0
0

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

1
1
19 votes
19 votes

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

4 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!
0
0

@Amcodes What if tree becomes unbalanced after Insertion

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

0
0

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

0
0
Great Answer
0
0
14 votes
14 votes
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 .........

2 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..
0
0

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.

1
1
0 votes
0 votes
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

4 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.
2
2
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.
0
0
Heap is not possible because for insertion we need to check element is present or not so it will take O(n) time
2
2
Answer:

Related questions