What data structure is required for storing a set of integers such that, deletion of the smallest element and, insertion of an element if not already present in the set, can be done in $O(\log n)$ time?

Your answer seems reasonable.
Find out if you're right!