# 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.) – Isiah Meadows Dec 11 '16 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 '16 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.) – Isiah Meadows Dec 12 '16 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 '16 at 6:02
• I don't see how that's possible, it would give you an O(n) sorting algorithm. – Albert Hendriks Dec 13 '16 at 6:22