Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 428058.0, MPI für Informatik / Algorithms and Complexity Group
Multipartite Priority Queues
Authors:Elmasry, Amr; Jensen, Claus; Katajainen, Jyrki
Language:English
Date of Publication (YYYY-MM-DD):2008
Title of Journal:ACM Transactions on Algorithms
Volume:5
Issue / Number:1
Start Page:14.1
End Page:19
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2009-03-24
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI f�r Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C125756E0038A185-D5DD03E5E5C9CA35C1257560006445AF-...
URL:http://doi.acm.org/10.1145/1435375.1435389
DOI:10.1145/1435375.1435389
ISSN:1549-6325
Full Text:
You have privileges to view the following file(s):
ACM-final.pdf   Uploading file not finished...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.