Editing Priority queue (section)

=== Using a sorting algorithm to make a priority queue ===

A sorting algorithm can also be used to implement a priority queue. Specifically, Thorup says:<ref>{{Cite journal | last1 = Thorup | first1 = Mikkel | author-link1 = Mikkel Thorup | year = 2007 | title = Equivalence between priority queues and sorting | journal = [[Journal of the ACM]] | volume = 54 | issue = 6 | page = 28 | doi = 10.1145/1314690.1314692 | s2cid = 11494634 }}</ref>

<blockquote>
We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to ''n'' keys in ''S''(''n'') time per key, then there is a priority queue supporting ''delete'' and ''insert'' in ''O''(''S''(''n'')) time and ''find-min'' in constant time.
</blockquote>

That is, if there is a sorting algorithm which can sort in ''O''(''S'') time per key, where ''S'' is some function of ''n'' and [[word size]],<ref>{{cite web |url=http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |title=Archived copy |access-date=2011-02-10 |url-status=live |archive-url=https://web.archive.org/web/20110720000413/http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |archive-date=2011-07-20 }}</ref> then one can use the given procedure to create a priority queue where pulling the highest-priority element is ''O''(1) time, and inserting new elements (and deleting elements) is ''O''(''S'') time. For example, if one has an ''O''(''n''&nbsp;log&nbsp;''n'') sort algorithm, one can create a priority queue with ''O''(1) pulling and ''O''(&nbsp;log&nbsp;''n'') insertion.