Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | 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*:

Elmasry2008b

Title

Title*:

Multipartite Priority Queues


ACM-final.pdf (176.11 KB)

Journal

Journal Title*:

ACM Transactions on Algorithms
Journal's URL:

http://talg.acm.org/

Download URL
for the article:

http://delivery.acm.org/10.1145/1440000/1435389/a14-elmasry.pdf?key1=1435389&key2=3608984321&coll=portal&dl=ACM&CFID=22957209&CFTOKEN=87484811
Language:

English

Publisher

Publisher's
Name:

Association for Computing Machinery (ACM)
Publisher's URL:

http://www.acm.org/

Publisher's
Address:

New York, USA
ISSN:

1549-6325

Vol, No, pp, Date

Volume*:

5
Number:

1

Publishing Date:

November 2008

Pages*:

1-19
Number of
VG Pages:

19

Page Start:

1
Page End:

19

Sequence Number:

14
DOI:

10.1145/1435375.1435389

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We introduce a framework for reducing the number of element
comparisons performed in priority-queue operations. In particular, we
give a priority queue which guarantees the worst-case cost of $O(1)$
per minimum finding and insertion, and the worst-case cost of $O(\log
n)$ with at most $\log n + O(1)$ element comparisons per minimum
deletion and deletion, improving the bound of $2\log n + O(1)$ known for
binomial queues. Here, $n$ denotes the number of elements stored in the
data structure prior to the operation in question, and $\log n$ equals
$\log_2(\max\set{2, n})$. As an immediate application of the priority queue
developed, we obtain a sorting algorithm that is optimally adaptive with
respect to the inversion measure of disorder, and that sorts a sequence
having $n$ elements and $I$ inversions with at most $n \log (I/n) + O(n)$
element comparisons.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1435375.1435389&coll=portal&dl=ACM&idx=J982&part=transaction&WantType=Transactions&title=ACM%20Transactions%20on%20Algorithms%20%28TALG%29&CFID=22957209&CFTOKEN=87484811

Categories,
Keywords:

Priority Queues, Heaps, Meticulous Analysis, Constant Factors

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{Elmasry2008b,
AUTHOR = {Elmasry, Amr and Jensen, Claus and Katajainen, Jyrki},
 TITLE = {Multipartite Priority Queues},
 JOURNAL = {ACM Transactions on Algorithms},
 PUBLISHER = {Association for Computing Machinery (ACM)},
 YEAR = {2008},
 NUMBER = {1},
 VOLUME = {5},
 PAGES = {1--19},
 ADDRESS = {New York, USA},
 MONTH = {November},
 ISBN = {1549-6325},
 DOI = {10.1145/1435375.1435389},
}

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 19:15:14
Revision
1.
0.


Editor
Amr Elmasry
Amr Elmassry


Edit Date
03/17/2009 04:36:35 PM
02/17/2009 07:15:14 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

File Attachment Icon
ACM-final.pdf