Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Elmasry, Amr
Jensen, Claus
Katajainen, Jyrki

dblp
dblp
dblp

Not MPG Author(s):

Jensen, Claus
Katajainen, Jyrki

BibTeX cite key*:

Elmasry2008c

Title

Title*:

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


fulltext.pdf (718.08 KB); ATTUSH4Y.pdf (718.08 KB)

Journal

Journal Title*:

Computing

Journal's URL:

http://www.springerlink.com/content/103076/

Download URL
for the article:

http://www.springerlink.com/content/9g83763074222771/fulltext.pdf

Language:

English

Publisher

Publisher's
Name:

Springer Wein

Publisher's URL:

http://www.springerlink.com/home/main.mpx

Publisher's
Address:

Berlin, Germany

ISSN:

1436-5057

Vol, No, pp, Date

Volume*:

83

Number:

4

Publishing Date:

November 2008

Pages*:

193-204

Number of
VG Pages:

12

Page Start:

193

Page End:

204

Sequence Number:


DOI:

10.1007/s00607-008-0019-2

Note, Abstract, ©

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

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Elmasry2008c,
AUTHOR = {Elmasry, Amr and Jensen, Claus and Katajainen, Jyrki},
TITLE = {Two New Methods for Constructing Double-Ended Priority Queues from Priority Queues},
JOURNAL = {Computing},
PUBLISHER = {Springer Wein},
YEAR = {2008},
NUMBER = {4},
VOLUME = {83},
PAGES = {193--204},
ADDRESS = {Berlin, Germany},
MONTH = {November},
ISBN = {1436-5057},
DOI = {10.1007/s00607-008-0019-2},
}


Entry last modified by Amr Elmasry, 03/17/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Amr Elmassry
Created
02/17/2009 08:28:40 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Amr Elmasry
Amr Elmasry
Amr Elmasry
Amr Elmasry
Amr Elmasry
Edit Dates
03/17/2009 04:57:44 PM
03/17/2009 04:52:02 PM
03/17/2009 04:42:26 PM
03/17/2009 04:37:26 PM
02/17/2009 08:30:38 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
fulltext.pdf
File Attachment Icon
ATTUSH4Y.pdf