A data structure is required for storing a set of integers such that each of…

Answer: A balanced binary search tree (for example, an AVL tree or a red–black tree) can be used; a plain heap alone cannot.

Reasoning:

• Balanced binary search tree: search, insertion and deletion all take O(log n) time when the tree is height-balanced. Deleting the smallest element is done by following left-child pointers to the leftmost node (O(log n)) and removing it (O(log n)). To insert only if not already present, first perform a search (O(log n)); if not found, insert (O(log n)). Hence both required operations run in O(log n).

• Heap (min-heap): delete-min and insertion are O(log n). However, checking whether an element is already present in a plain heap requires scanning elements in the worst case, which is O(n). Therefore a plain heap cannot guarantee the "insert only if not already present" operation in O(log n).

• Note: If you combine a heap with an auxiliary structure (for example, a hash table or an index map) you can get fast membership checks, but that uses multiple data structures. The question asks for a single data structure that supports both operations in O(log n), so a balanced BST is the appropriate choice.