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.

  • $\begingroup$ 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.) $\endgroup$
    – Claudia
    Dec 11, 2016 at 2:08
  • $\begingroup$ 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. ​ ​ $\endgroup$
    – user12859
    Dec 12, 2016 at 3:20
  • $\begingroup$ 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.) $\endgroup$
    – Claudia
    Dec 12, 2016 at 9:50
  • $\begingroup$ @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. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Dec 13, 2016 at 6:02
  • $\begingroup$ I don't see how that's possible, it would give you an O(n) sorting algorithm. $\endgroup$ Dec 13, 2016 at 6:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.