3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why wouldn't such a data structure not violate the famous lower bound on sorting? $\endgroup$ – Raphael Apr 21 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 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 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 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 at 14:40
2
$\begingroup$

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.

$\endgroup$
  • $\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 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 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 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 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 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.