# Unique integer priority queue with both $O(1)$ insert and extract-min?

I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do both insert and extract-min in $O(1)$? The closest one I've found so far is this one, with the following qualities:

• Insert: $O(1)$
• Extract-min: $O(\log \log n)$

None of the other operations need to be any quicker than what's sane for a few dozen unit tests with very small numbers. I'd prefer space to be no more than log-linear, though, given my use case (not absolute, but they're very frequently created and destroyed).

Note that the n will need to change every so often, but I plan on placing it in a resizable array with amortized linear growth and shrinking, so that shouldn't affect much.

Edit: I've found that for my purposes, a hash map + bitset is sufficient (it was for fast and low-memory unique ID generation), so this question more remains out of curiosity.

• I'm okay with amortized time for growing the queue, but I'd prefer against amortized for acquiring when there is one that exists. (This is for something soft real time.) Dec 11, 2016 at 2:08
• This paper shows that a model called “RAMBO” with multiplication/division bypasses the cell probe lower bounds to get worst-case O(1) for a whole bunch of priority queue operations simultaneously, including your two operations. ​ ​
– user12859
Dec 12, 2016 at 3:20
• Well...too bad I need a pure software implementation of this. (BTW, could you fix the formatting of your post? It'd be much easier to follow if you did - the Markdown rendering is not exactly easy to read.) Dec 12, 2016 at 9:50
• @D.W. : ​ ​ ​ How does that work? ​ It seems like one would in turn get amortized linear time sorting in which one must give all of each output before seeing any of the next input. ​ ​ ​ ​ ​ ​ ​ ​
– user12859
Dec 13, 2016 at 6:02
• I don't see how that's possible, it would give you an O(n) sorting algorithm. Dec 13, 2016 at 6:22