Editing Priority queue (section)

=== Usual implementation ===

To improve performance, priority queues are typically based on a [[Heap (data structure)|heap]], giving ''O''(log ''n'') performance for inserts and removals, and ''O''(''n'') to build the [[Heap (data structure)|heap]] initially from a set of ''n'' elements. Variants of the basic heap data structure such as [[pairing heap]]s or [[Fibonacci heap]]s can provide better bounds for some operations.<ref name="CLRS_priority_queue_pp476">{{Introduction to Algorithms|edition=2|chapter=Chapter 20: Fibonacci Heaps|pages=476–497}} Third edition, p. 518.</ref>

Alternatively, when a [[self-balancing binary search tree]] is used, insertion and removal also take ''O''(log ''n'') time, although building trees from existing sequences of elements takes ''O''(''n'' log ''n'') time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries. From a space-complexity standpoint, using [[self-balancing binary search tree]] with [[linked list]] takes more storage, since it requires to store extra references to other nodes.

From a computational-complexity standpoint, priority queues are congruent to sorting algorithms. The section on [[#Equivalence of priority queues and sorting algorithms|the equivalence of priority queues and sorting algorithms]], below, describes how efficient sorting algorithms can create efficient priority queues.