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.
$\begingroup$
$\endgroup$
-
1$\begingroup$ Why wouldn't such a data structure not violate the famous lower bound on sorting? $\endgroup$ – Raphael♦ Apr 21 '19 at 12:11
-
$\begingroup$ @Raphael Numbers in the range $\{1,\ldots,n\}$ can be sorted in linear time using counting sort. $\endgroup$ – Yuval Filmus Apr 21 '19 at 12:16
-
$\begingroup$ I added an assumption that you will be sorting a maximum of n elements if that can help. $\endgroup$ – Shanksme Apr 21 '19 at 12:35
-
$\begingroup$ You may be interested in a radix heap, which has similar properties to what you're looking for. $\endgroup$ – ryan Apr 21 '19 at 14:25
-
$\begingroup$ @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. $\endgroup$ – Shanksme Apr 21 '19 at 14:40
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ 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. $\endgroup$ – ryan Apr 21 '19 at 20:41
-
$\begingroup$ @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). $\endgroup$ – D.W.♦ Apr 21 '19 at 22:36
-
$\begingroup$ 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. $\endgroup$ – ryan Apr 21 '19 at 22:39
-
$\begingroup$ @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? $\endgroup$ – D.W.♦ Apr 21 '19 at 22:43
-
$\begingroup$ 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. $\endgroup$ – ryan Apr 21 '19 at 22:49
