Two new methods for constructing double-ended priority queues from priority queues
Research output: Contribution to journal › Journal article › Research › peer-review
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 {lgm, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.
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 {lgm, lg n}) for meld. Here, m and n denote the number of elements stored in the data structures prior to the operation in question.
Original language | English |
---|---|
Journal | Computing |
Volume | 83 |
Issue number | 4 |
Pages (from-to) | 193-204 |
Number of pages | 13 |
ISSN | 0010-485X |
DOIs | |
Publication status | Published - 2008 |
ID: 10922783