| 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... |
|
Advanced
