edited by
20,114 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

edited by

4 Answers

Best answer
92 votes
92 votes

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

Related questions

25 votes
25 votes
3 answers
1
Kathleen asked Sep 16, 2014
23,358 views
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...
27 votes
27 votes
6 answers
3
Kathleen asked Sep 18, 2014
22,413 views
The following numbers are inserted into an empty binary search tree in the given order: $10, 1, 3, 5, 15, 12, 16$. What is the height of the binary search tree (the heigh...
44 votes
44 votes
5 answers
4