Note: |
|
(LaTeX) 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. |
URL for the Abstract: |
|
Categories,
Keywords: |
Data Structures, Priority Queues, Double-Ended Priority Queues, Min-Max Priority Queues, Priority Deques, Meticulous Analysis |
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Public |
|