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

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