Most efficient known priority queue for inserts - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:32:41Z https://cs.stackexchange.com/feeds/question/2824 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/2824 2 Most efficient known priority queue for inserts A T https://cs.stackexchange.com/users/1120 2012-07-19T15:49:47Z 2013-01-05T08:59:24Z <p>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.</p> <p><sub> If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: <a href="https://cs.stackexchange.com/q/524">Does there exist a priority queue with $O(1)$ extracts?</a>. </sub></p> https://cs.stackexchange.com/questions/2824/-/2825#2825 2 Answer by A T for Most efficient known priority queue for inserts A T https://cs.stackexchange.com/users/1120 2012-07-19T15:49:47Z 2012-07-27T10:50:38Z <h3>Worst-case complexity</h3> <p><strong>Insert</strong>: $\mathcal{O}(1)$</p> <p><strong>Find-min</strong>: $\mathcal{O}(1)$</p> <p><strong>Decrease-key</strong>: $\mathcal{O}(1)$</p> <p><strong>Delete</strong>: $\mathcal{O}(\log \log n)$</p> <p><strong>Space</strong>: $\mathcal{O}(n)$</p> <h3>Proof</h3> <blockquote> <p>THEOREM 1. <em>We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting</em> <strong>ﬁnd-min</strong>, <strong>insert</strong>, <em>and</em> <strong>dec-key</strong> <em>in constant time, and</em> <strong>delete</strong> <em>in $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$ time.</em></p> </blockquote> <p>Which is established with a combination of:</p> <blockquote> <p>LEMMA 3. <em>Let $\tau(n, N)$ be the</em> <strong>delete</strong> <em>time for a priority queue for up to $n$ integers in the range $[0 , N)$ supporting</em> <strong>insert</strong> <em>and</em> <strong>dec-key</strong> <em>in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.</em></p> </blockquote> <p>and:</p> <blockquote> <p>THEOREM 6. <em>Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $[0 , N)$ in linear space supporting <strong>ﬁnd-min</strong>, <strong>insert</strong>, and <strong>dec-key</strong> in constant time, and <strong>delete</strong> in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.</em></p> </blockquote> <h3>Reference</h3> <p><a href="http://doi.acm.org/10.1145/780542.780566" rel="nofollow">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.</a></p> https://cs.stackexchange.com/questions/2824/-/2871#2871 2 Answer by Shahbaz for Most efficient known priority queue for inserts Shahbaz https://cs.stackexchange.com/users/944 2012-07-23T09:41:55Z 2012-12-15T06:42:59Z <p>Like with anything in CS, there is no "best something". There are always trade offs. But, perhaps this section of <a href="http://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times" rel="nofollow">Wikipedia's article on Fibonacci heap</a> could help you:</p> <p><a href="http://en.wikipedia.org/wiki/Fibonacci_heap" rel="nofollow">Fibonacci heap</a>: Amortized $\mathcal{O}(\log\ n)$ delete and delete_min, amortized $\mathcal{O}(1)$ decrease_key and $\mathcal{O}(1)$ the rest.</p> <p><a href="http://en.wikipedia.org/wiki/Brodal_queue" rel="nofollow">Brodal queue</a>: Worst-case $\mathcal{O}(\log\ n)$ delete and delete_min, $\mathcal{O}(1)$ the rest.</p> <p><a href="http://en.wikipedia.org/wiki/Pairing_heap" rel="nofollow">Pairing heap</a>: 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.</p> https://cs.stackexchange.com/questions/2824/-/7404#7404 0 Answer by A T for Most efficient known priority queue for inserts A T https://cs.stackexchange.com/users/1120 2012-12-15T04:04:14Z 2012-12-15T04:04:14Z <p>Finally a simplification of the Brodal queue has been released, which unlike; are worst-case values (rather than amortised).</p> <p><strong>Insert</strong>: $\mathcal{O}(1)$</p> <p><strong>Find-min</strong>: $\mathcal{O}(1)$</p> <p><strong>Decrease</strong>: $\mathcal{O}(1)$</p> <p><strong>Meld</strong>: $\mathcal{O}(1)$</p> <p><strong>Delete-min</strong>: $\mathcal{O}(log\ n)$, that's equivalent to $\approx 70\ log\ n$ here, which is a smaller constant than Brodal.</p> <hr> <p> <a href="http://dl.acm.org/citation.cfm?id=313852.313883" rel="nofollow">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.</a></p> <p> <a href="http://dx.doi.org/10.1007/978-3-642-30642-6_13" rel="nofollow">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.</a></p> <p> <a href="http://dl.acm.org/citation.cfm?id=1765751.1765758" rel="nofollow">Takaoka, Tadao. “Theory of 2-3 Heaps.” In In Computing and Combinatorics, Volume 1627 of LNCS, 41–50. Springer, 1999.</a></p> https://cs.stackexchange.com/questions/2824/-/7768#7768 0 Answer by A T for Most efficient known priority queue for inserts A T https://cs.stackexchange.com/users/1120 2013-01-04T19:51:24Z 2013-01-04T19:51:24Z <h3>Worst-case complexity</h3> <p>$\mathcal{O}(log\ M)$ insert, search, delete [see 'Lemma 3.1']</p> <p>$\dagger\ \mathcal{O}(1)$ findMin, findMax, extractMin, extractMax, predecessor, successor</p> <p>$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]</p> <p>(where $M$ is the bounded integer universe: $M = [0, \cdots, M - 1]$</p> <h3>Question about my analysis of the paper</h3> <p>$\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}.</p> <hr> <p>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)</p> https://cs.stackexchange.com/questions/2824/-/7780#7780 0 Answer by A T for Most efficient known priority queue for inserts A T https://cs.stackexchange.com/users/1120 2013-01-05T08:59:24Z 2013-01-05T08:59:24Z <h3>Worst-case complexity</h3> <p><strong>$\boldsymbol{\mathcal{O}(1)}$ insertion</strong></p> <p><strong>$\boldsymbol{\mathcal{O}(log\ \textbf{min}\{w_x, q_x\})}$ get-min, extract-min, delete, and decrease of an element $\boldsymbol{x}$</strong></p> <p>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.</p> <p><a href="http://dx.doi.org/10.1016/j.jda.2012.04.014." rel="nofollow">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.</a> <a href="http://dx.doi.org/10.1016/j.jda.2012.04.014." rel="nofollow">1</a> </p>