Since 2014
Fast Meldable Priority Queues
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Fast Meldable Priority Queues
|
|
| Creator |
Brodal, Gerth Stølting
|
|
| Description |
We present priority queues that support the operations MakeQueue,FindMin, Insert and Meld in worst case time O(1) and Delete andDeleteMin in worst case time O(log n). They can be implemented on thepointer machine and require linear space. The time bounds are optimal forall implementations where Meld takes worst case time o(n).To our knowledge this is the first priority queue implementation thatsupports Meld in worst case constant time and DeleteMin in logarithmictime.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1995-01-12
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19515
10.7146/brics.v2i12.19515 |
|
| Source |
BRICS Report Series; No 12 (1995): RS-12 Fast Meldable Priority Queues
BRICS Report Series; No 12 (1995): RS-12 Fast Meldable Priority Queues 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19515/17136
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|