Editing Priority queue (section)

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

|}