Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
3  
Could you expand a the intent/question more? How does the motivation for this question differ from the link you provided? –  Nicholas Mancuso Jul 19 '12 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 '12 at 7:01
2  
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 '12 at 12:46
    
I modified my answer, but very suprised how much this question is being downvoted still :/ –  A T Jul 23 '12 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 '12 at 18:46

5 Answers 5

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.

share|improve this answer
    
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 '12 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 '12 at 7:02
1  
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. –  edA-qa mort-ora-y Jul 27 '12 at 12:49
1  
@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 '12 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). –  edA-qa mort-ora-y Jul 27 '12 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.

share|improve this answer
    
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 '12 at 18:49
    
@AT, then maybe try adding it to Wikipedia? ;) –  Shahbaz Jul 24 '12 at 7:42

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)

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.