Editing Priority queue (section)

== Equivalence of priority queues and sorting algorithms ==

=== Using a priority queue to sort ===

The [[operational semantics|semantics]] of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several [[sorting algorithm]]s, once the layer of [[abstraction (computer science)|abstraction]] provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms:

{|class="wikitable sortable"

! Name !! Priority Queue Implementation !! Best !! Average !! Worst 
|- align="center"
| [[Heapsort]]
| [[Heap (data structure)|Heap]]
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''

|- align="center"
| [[Smoothsort]]
| Leonardo Heap
|style="background:#dfd"|''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''

|- align="center"
| [[Selection sort]]
| Unordered [[Array#In computer science|Array]]
|style="background:#fdd"|''n<sup>2</sup>''
|style="background:#fdd"|''n<sup>2</sup>''
|style="background:#fdd"|''n<sup>2</sup>''

|- align="center"
| [[Insertion sort]]
| Ordered [[Array#In computer science|Array]]
|style="background:#dfd"|''n''
|style="background:#fdd"|''n<sup>2</sup>''
|style="background:#fdd"|''n<sup>2</sup>''

|- align="center"
| [[Tree sort]]
| [[Self-balancing binary search tree]]
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''
|style="background:#dfd"|''n''&nbsp;log&nbsp;''n''

|}

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