A data structure is required for storing a set of integers such that each of the following O(log n) operations can be done in time, where n is the number of elements in the set. Deletion of the smallest element 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. AA heap can be used but not a balanced binary search tree.
2. BA balanced binary search tree can be used but not a heap.
3. CBoth balanced binary search tree and heap can be used.
4. DNeither balanced binary search tree nor heap can be used.

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. A balanced binary search tree can be used but not a heap.

Explanation

A heap deletes the minimum in O(log n) but cannot check 'not already present' faster than O(n). A balanced BST does both in O(log n).