4.8k views

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

edited | 4.8k views
0

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
Is worst case time complexity for general insert in heap is O(n) and for min or max heap it is O(logn)?
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?

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

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

edited
+2

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
As we need to delete the first element as you said, yes which takes O(1) time,but  here deletion takes place by replacing  the first element with last and last element is deleted, then we call heapify to adjust our min heap which takes logn time so total is logn time in deletion of min element.
+10
it will be O(log n) because u have to keep moving left from the root till u cannot go any longer and hence u will travel log n levels to delete the smallest element in balanced binary search tree.
+1
Why is skewed tree not considered here ? In skewed binary search tree, searching and inserting will be O(n).
+6
answer is balanced binary search tree a skew tree is not balanced binary search tree as balancing factor can be more than 1.
+1

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

@jaisyking YES.

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

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..
ans b)
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
0
But how will we identify the smallest element on a max-heap?
+1
Sorry , it too will take O(⎣logn⎦) times to search min element in max heap and then delete that. So total complexity here also O(logn).( For both min and max heap)
0
It will be O(n) to get the min element in a max heap rt?
0
why O(n) ?
+8
Because we just know that the smallest element is in the last level of max heap. And in last level there can be up to n/2 elements. And they are not sorted. So, we need min n/2-1 comparisons.
+2
Yes Sir , sorry I was wrong

It says too  http://www.geeksforgeeks.org/data-structures-and-algorithms-set-7/

Thank you for clearing  me up

Then only balanced binary search tree will be the answer (B)
+1
No, heap should also do, just that we have to use min-heap. (C) should be the answer.
+1
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.
0
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.
+1
Heap is not possible because for insertion we need to check element is present or not so it will take O(n) time

1
2