| Multipartite priority queues | |
| Authors: | Amr Elmasry, Claus Jensen, and Jyrki Katajainen |
| Published in: | ACM Transactions on Algorithms 5,1 (2008), Article 14, 19 pp. |
| Full text: |  PDF (231 kB)  PS (814 kB) |
| DOI: | 10.1145/1435375.1435389 |
| Copyright: | © ACM |
| 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 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 log2(max{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. |
| Related: |  HTML (Technical report) HTML (Later version) |
| BibLATEX: | @article{EJK2008cJ,
author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
title = {Multipartite priority queues},
journaltitle = {ACM Transactions on Algorithms},
volume = {5},
number = {1},
year = {2008},
articleno = {14},
pagetotal = {19},
}
|