Thumbnail
Access Restriction
Subscribed

Author Thorup, Mikkel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Priority queues ♦ Sorting
Abstract We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to $\textit{n}$ keys in $\textit{S}(\textit{n})$ time per key, then there is a priority queue supporting delete and insert in $\textit{O}(\textit{S}(\textit{n}))$ time and find-min in constant time. Conversely, a priority queue can trivially be used for sorting: first insert all keys to be sorted, then extract them in sorted order by repeatedly deleting the minimum. Asymptotically, this settles the complexity of priority queues in terms of that of sorting. Previously, at SODA'96, such a result was presented by the author for the special case of monotone priority queues where the minimum is not allowed to decrease. Besides nailing down the complexity of priority queues to that of sorting, and vice versa, our result yields several improved bounds for linear space integer priority queues with find-min in constant time: $\textit{Deterministically}.$ We get $\textit{O}(log$ log $\textit{n})$ update time using a sorting algorithm of Han from STOC'02. This improves the $\textit{O}((log$ log $\textit{n})(log$ log log $\textit{n}))$ update time of Han from SODA'01. $\textit{Randomized}.$ We get $\textit{O}(&sqrt;log$ log $\textit{n})$ expected update time using a randomized sorting algorithm of Han and Thorup from FOCS'02. This improves the $\textit{O}(log$ log $\textit{n})$ expected update time of Thorup from SODA'96. Deterministically in $AC^{0}$ (without multiplication). For any ϵ > 0, we get $\textit{O}((log$ log $n)^{1+ϵ})$ update time using an $AC^{0}$ sorting algorithm of Han and Thorup from FOCS'02. This improves the $\textit{O}((log$ log $n)^{2})$ update time of Thorup from SODA'98. Randomized in $AC^{0}.$ We get $\textit{O}(log$ log $\textit{n})$ expected update time using a randomized $AC^{0}$ sorting algorithm of Thorup from SODA'97. This improves the $\textit{O}((log$ log $n)^{1+ϵ})$ expected update time of Thorup also from SODA'97. The above bounds assume that each integer is stored in a single word and that word operations take unit time as in the word RAM.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-12-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 54
Issue Number 6


Source: ACM Digital Library