Is it possible to have a data structure that supports both insertion and delete-min (or max) in $O(1)$?
You can assume the numbers that will be inserted are integers in the range [0,n] and that you will be inserting a maximum of n elements.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs it possible to have a data structure that supports both insertion and delete-min (or max) in $O(1)$?
You can assume the numbers that will be inserted are integers in the range [0,n] and that you will be inserting a maximum of n elements.
No; at least, it seems unlikely. Such a data structure would contradict the lower bound on comparison-based sorting algorithms and would imply linear-time sorting algorithms (where none is known to exist).
Suppose we want to sort $m$ numbers from the range $1..n$, where $m \ll n$. If we had your data structure, we could do that in $O(m)$ time. However, this seems implausible. The fastest comparison-based algorithm runs in time $\Theta(m \log m)$, which is larger than $O(m)$. Counting sort takes $O(m+n)$ time, which is much larger than $O(m)$ when $m \ll n$. Van Emde Boas sorting takes $O(m \log \log n)$ time, which is still larger than $O(m)$ time. Han & Thorup's sorting algorithm takes $O(m \sqrt{\log \log n})$ time, which is still larger than $O(m)$ time.
So, you should not expect there to be any data structure of the form you list, as that would imply a huge breakthrough in sorting algorithms.
However, there is probably an algorithm where those operations can be done in $O(\log \log n)$ time, or possibly even $O(\sqrt{\log \log n})$ time, by applying Van Emde Boas trees or Han & Thorup. See also https://en.wikipedia.org/wiki/Integer_sorting#Sorting_versus_integer_priority_queues.