English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Two New Methods for Constructing Double-ended Priority Queues from Priority Queues

MPS-Authors
/persons/resource/persons44380

Elmasry,  Amr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Elmasry, A. (2008). Two New Methods for Constructing Double-ended Priority Queues from Priority Queues. Computing, 83(4), 193-204. doi:10.1007/s00607-008-0019-2.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1D4F-8
Abstract
We introduce two data-structural transformations to construct double-ended priority queues from priority queues. To apply our transformations the priority queues exploited must support the extraction of an unspecified element, in addition to the standard priority-queue operations. With the first transformation we obtain a double-ended priority queue which guarantees the worst-case cost of $O(1)$ for \Findmin{}, \Findmax{}, \Insert{}, \Extract{}; and the worst-case cost of $O(\lg n)$ with at most $\lg n + O(1)$ element comparisons for \Delete{}. With the second transformation we get a meldable double-ended priority queue which guarantees the worst-case cost of $O(1)$ for \Findmin{}, \Findmax{}, \Insert{}, \Extract{}; the worst-case cost of $O(\lg n)$ with at most $\lg n + O(\lg \lg n)$ element comparisons for \Delete{}; and the worst-case cost of $O(\min\set{\lg m, \lg n})$ for \Meld{}. Here, $m$ and $n$ denote the number of elements stored in the data structures prior to the operation in question.