### Equivalence between priority queues and sortingEquivalence between priority queues and sorting

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