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

Question

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.

• Claudia: 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.)
• user12859: 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. ​ ​
• Claudia: 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.)
• user12859: @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. ​ ​ ​ ​ ​ ​ ​ ​
• Albert Hendriks: I don't see how that's possible, it would give you an O(n) sorting algorithm.