# Data structure with insert, and delete-min (or max) in $O(1)$?

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.

• Why wouldn't such a data structure not violate the famous lower bound on sorting? – Raphael Apr 21 '19 at 12:11
• @Raphael Numbers in the range $\{1,\ldots,n\}$ can be sorted in linear time using counting sort. – Yuval Filmus Apr 21 '19 at 12:16
• I added an assumption that you will be sorting a maximum of n elements if that can help. – Shanksme Apr 21 '19 at 12:35
• You may be interested in a radix heap, which has similar properties to what you're looking for. – ryan Apr 21 '19 at 14:25
• @ryan Interesting, but there is this condition that poses a problem : The radix heap is a monotone priority queue. A monotone priority queue is a priority queue with the restriction that a key cannot be pushed if it is less than the last key extracted from the queue. – Shanksme Apr 21 '19 at 14:40

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.

• If you assume $m = n$ in the worst case, then I don't see how this suggests such a data structure cannot exist. As you say, counting sort would take $O(n)$, and thus it seems plausible to me. For instance, a simple "counting array" could handle $n$ inserts easily, then handle $n$ delete-mins easily. All this is in $O(n)$. The question seems to be, how does the complexity change when we intermingle these operations, for which I still think $O(n)$ should be possible. – ryan Apr 21 '19 at 20:41
• @ryan For the answer to be "Yes", we need a data structure that runs in $O(1)$ time for all $m,n$ -- not just for the special case where $m=n$. I show that if it runs in $O(1)$ time for all $m,n$, then that has implausible consequences. To put it another way: it might be easier to create a data structure that is fast for the special case where $m=n$ than for the case where $m=\sqrt{n}$ (say); I am showing that the latter case is hard. That's enough to show that the answer to the question in the post is "No" (barring a breakthrough in integer sorting). – D.W. Apr 21 '19 at 22:36
• Fair enough, I think a more interesting question would be if you could have such a data structure where for any $m$, $n$, you could do a sequence of $m$ inserts / delete-mins in $O(n)$ time. Thus, making each operation $O(n\ /\ m)$ amortized. – ryan Apr 21 '19 at 22:39
• @ryan, that could be interesting too. Perhaps this paper could be relevant to that question? (when paired with counting sort) Want to ask it as a separate question and see if anyone finds a solution? – D.W. Apr 21 '19 at 22:43
• I'm going to read through this paper for a bit to see if anything comes up that may help, then I'll post. This paper looks promising. – ryan Apr 21 '19 at 22:49