# Most efficient known priority queue for inserts

In terms of asymptotic space and time complexity, what is the most efficient priority-queue? Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes are a little slower.

If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: Does there exist a priority queue with $O(1)$ extracts?.

• Could you expand a the intent/question more? How does the motivation for this question differ from the link you provided? Jul 19, 2012 at 18:28
• The link I provided refers to a request for a priority-queue supporting $\mathcal{O}(1)$ extracts, whereas this one is maximising the other operations first and foremost.
– A T
Jul 20, 2012 at 7:01
• It is not clear that a "most efficient" implementation exists. There may be many that are not dominated by any other in all categories. So without more restriction, the question is likely not very meaningful. In any case, you should probably ask for the best known ones.
– Raphael
Jul 20, 2012 at 12:46
• I modified my answer, but very suprised how much this question is being downvoted still :/
– A T
Jul 23, 2012 at 8:55
• @Juho: No, actually. I want to minimze the complexity of all attributes, maximising (focussing) on improving (decreasing) the complexity of inserts over deletes, as opposed to the referenced question.
– A T
Jul 23, 2012 at 18:46

### Worst-case complexity

Insert: $$\mathcal{O}(1)$$

Find-min: $$\mathcal{O}(1)$$

Decrease-key: $$\mathcal{O}(1)$$

Delete: $$\mathcal{O}(\log \log n)$$

Space: $$\mathcal{O}(n)$$

### Proof

THEOREM 1. We can implement a priority queue that with n integer keys in the range $$[0 , N )$$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $$\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$$ time.

Which is established with a combination of:

LEMMA 3. Let $$\tau(n, N)$$ be the delete time for a priority queue for up to $$n$$ integers in the range $$[0 , N)$$ supporting insert and dec-key in constant time. Then $$\tau ( n, N ) \le τ ( N, N)$$. This holds whether $$\tau$$ is amortized or worst-case.

and:

THEOREM 6. Theorem 6. We can implement a priority queue that with $$n$$ integer keys in the range $$[0 , N)$$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $$\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$$ time for a key of rank $$q$$.

### Reference

Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC ’03. New York, NY, USA: ACM, 2003.

• Why can't we do better? As I understand it, the question is specifically asking for an optimal data structure, or perhaps optimal tradeoffs if you will.
– Juho
Jul 19, 2012 at 19:57
• I'm sure we can do better. Revisit this question soon and you'll see some answers showing more efficient priority-queues :)
– A T
Jul 20, 2012 at 7:02
• This would imply a sorting algorithm better than $O(n log n)$ since you you could simply insert all items, find-min and delete n times, giving you $O(n log log n)$ time. Jul 27, 2012 at 12:49
• @edA-qamort-ora-y That's not a problem since there are such algorithms. The crucial fact (that really should be emphasized here I think) is that the priority-queue here is for exactly integers in a specific range. Likewise consider perhaps a more familiar case of sorting with a vEB-tree. With integers in the range $0$ to $M-1$ one can easily sort in $O(n \log \log M)$ time.
– Juho
Jul 27, 2012 at 14:09
• That makes sense. I should have though about the sorting limit more, since I've actually implemented the vEB tree (well,a trie, or radix, which appears to be similar in nature and have the same complexity). Jul 27, 2012 at 17:31

Like with anything in CS, there is no "best something". There are always trade offs. But, perhaps this section of Wikipedia's article on Fibonacci heap could help you:

Fibonacci heap: Amortized $\mathcal{O}(\log\ n)$ delete and delete_min, amortized $\mathcal{O}(1)$ decrease_key and $\mathcal{O}(1)$ the rest.

Brodal queue: Worst-case $\mathcal{O}(\log\ n)$ delete and delete_min, $\mathcal{O}(1)$ the rest.

Pairing heap: Amortized $\mathcal{O}(\log\ n)$ delete and delete_min, unknown decrease_key, but bounded by $\mathcal{\Omega}(\log \log\ n)$, amortized $2^{\mathcal{O}(\sqrt{\log\log\ n})}$, $\mathcal{O}(1)$ the rest.

• Thanks, I've been looking at Brodal queues for a while, and recently got myself a copy of "Introduction to Algorithms" which has a nice section on Fibonacci heaps. If you look at my first-answer to this question, you'll see that all the complexities I've found for this certain priority-queue is better than all the ones you've referenced.
– A T
Jul 23, 2012 at 18:49
• @AT, then maybe try adding it to Wikipedia? ;) Jul 24, 2012 at 7:42

Finally a simplification of the Brodal queue has been released, which unlike; are worst-case values (rather than amortised).

Insert: $\mathcal{O}(1)$

Find-min: $\mathcal{O}(1)$

Decrease: $\mathcal{O}(1)$

Meld: $\mathcal{O}(1)$

Delete-min: $\mathcal{O}(log\ n)$, that's equivalent to $\approx 70\ log\ n$ here, which is a smaller constant than Brodal.

### Worst-case complexity

$$\mathcal{O}(log\ M)$$ insert, search, delete [see 'Lemma 3.1']

$$\dagger\ \mathcal{O}(1)$$ findMin, findMax, extractMin, extractMax, predecessor, successor

$$2M + \mathcal{O}(log\ M)$$ bits of ordinary memory and $$m$$ bits of Yggdrasdil memory [this second type of memory is defined in the paper]

(where $$M$$ is the bounded integer universe: $$M = [0, \cdots, M - 1]$$

### Question about my analysis of the paper

$$\dagger$$ Can someone confirm this result, as I am assuming it from 'Theorem 3.1'; i.e.: that "update" in 'Lemma 3.3' only refers to random inserts and deletes rather than extract{Min,Max}.

Brodnik, Andrej, Svante Carlsson, Michael L. Fredman, Johan Karlsson, and J. Ian Munro. “Worst Case Constant Time Priority Queue.” Journal of Systems and Software 78, no. 3 (2005): 249 – 256. doi:10.1016/j.jss.2004.09.002. (I read the 6 page version)

### Worst-case complexity

$$\boldsymbol{\mathcal{O}(1)}$$ insertion

$$\boldsymbol{\mathcal{O}(log\ \textbf{min}\{w_x, q_x\})}$$ get-min, extract-min, delete, and decrease of an element $$\boldsymbol{x}$$

Where $$w_x$$ (respectively, $$q_x$$) is the number of elements that were accessed after (respectively, before) the last access to $$x$$ and are still in the priority queue at the time when the corresponding operation is performed.