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.
Deletion of the smallest element
Which of the following data structures can be used for this purpose?
A balanced binary search tree can be used but not a heap
Both balanced binary search tree and heap can be used
Neither balanced search tree nor heap can be used
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)$)