Name
Abstract | ||
|---|---|---|
We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q* that supports find-min in constant time, insert in constant x-time, and delete in x-time O(t). Moreover, if Q supports dec-key in constant time, then so does Q*. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1077464.1077471 | ACM Transactions on Algorithms |
Keywords | Field | DocType |
priority queue q,shortest paths,constant x-time,simple black box,x-time o,constant-time insertion,constant time,priority queues,shortest path,priority queue | Black box (phreaking),Discrete mathematics,Combinatorics,Priority queue,Mathematics,Double-ended priority queue | Journal |
Volume | Issue | ISSN |
1 | 1 | 1549-6325 |
Citations | PageRank | References |
9 | 0.53 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephen Alstrup | 1 | 657 | 42.60 |
| Thore Husfeldt | 2 | 733 | 40.87 |
| Theis Rauhe | 3 | 661 | 35.11 |
| Mikkel Thorup | 4 | 5081 | 366.30 |