patternMinor
Data structure with insert, and delete-min (or max) in $O(1)$?
Viewed 0 times
insertdeletewithminmaxstructureanddata
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#107309, answer score: 2
Revisions (0)
No revisions yet.