Most efficient known priority queue for inserts

Question

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?.}

Answer 1

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 find-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 find-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.

Answer 2

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.

Answer 3

Finally a simplification of the Brodal queue[1] has been released[2], which unlike[3]; 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.

---

[1] Brodal, Gerth Stølting. “Worst-case Efficient Priority Queues.” In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 52–58. SODA ’96. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1996.

[2] Elmasry, Amr, and Jyrki Katajainen. “Worst-Case Optimal Priority Queues via Extended Regular Counters.” In Computer Science – Theory and Applications, edited by EdwardA. Hirsch, Juhani Karhumäki, Arto Lepistö, and Michail Prilutskii, 7353:125–137. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012.

[3] Takaoka, Tadao. “Theory of 2-3 Heaps.” In In Computing and Combinatorics, Volume 1627 of LNCS, 41–50. Springer, 1999.

Answer 4

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)

Answer 5

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.

A. Elmasry, A. Farzan, and J. Iacono, “A priority queue with the time-finger property,” J. of Discrete Algorithms, vol. 16, pp. 206–212, Oct. 2012. 1