We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Two new methods for constructing double-ended priority queues from priority queues.
- Authors
Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki
- 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 find-min, find-max, 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 find-min, find-max, 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 {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.
- Subjects
DATA structures; QUEUING theory; MANAGEMENT science; QUEUEING networks; ELECTRONIC data processing; MATHEMATICAL transformations
- Publication
Computing, 2008, Vol 83, Issue 4, p193
- ISSN
0010-485X
- Publication type
Article
- DOI
10.1007/s00607-008-0019-2