Editing Priority queue (section)

== Implementation ==

=== Naive implementations ===

One can create a simple, but inefficient priority queue in a number of ways. These naive implementations can demonstrate the expected behaviour of a priority queue in a simpler manner.

* ''insert'' elements into an unsorted array; find and ''extract'' element with ''highest priority''
*: Performance: "''insert''" performs in O(1) constant time, where "''extract_max''" performs in O(n) linear time.

 '''insert'''(element, priority):
     node.element ← element
     node.priority ← priority
     list.append(node)
 
 '''extract_max'''():
     highest ← 0
     foreach node in list:
         if highest.priority < node.priority:
             highest ← node
     list.remove(highest)
     return highest.element

* ''insert'' elements into a sorted array; ''extract'' first element
*: Performance: "''insert''" performs in O(n) linear time, where "''extract_max''" performs in O(1) constant time.

 '''insert'''(element, priority):
     node.element ← element
     node.priority ← priority
     for i in [0...N]:
         element ← list.get_at_index(i)
         if element.priority < node.priority:
             list.insert_at_index(node, i + 1)
             return
 
 '''extract_max'''():
     highest ← list.get_at_index(0)
     list.remove(highest)
     return highest.element

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

===Specialized heaps===
There are several specialized [[heap (data structure)|heap]] [[data structures]] that either supply additional operations or outperform heap-based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is {1, 2, ..., C}.

* When only ''insert'', ''find-min'' and ''extract-min'' are needed and in case of integer priorities, a [[bucket queue]] can be constructed as an array of {{mvar|C}} [[linked list]]s plus a pointer {{math|top}}, initially {{mvar|C}}. Inserting an item with key {{mvar|k}} appends the item to the {{mvar|k}}'th list, and updates {{math|top ← min(top, ''k'')}}, both in constant time. ''Extract-min'' deletes and returns one item from the list with index {{math|top}}, then increments {{math|top}} if needed until it again points to a non-empty list; this takes {{math|''O''(''C'')}} time in the worst case. These queues are useful for sorting the vertices of a graph by their degree.<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = The Algorithm Design Manual |publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4}}</ref>{{rp|374}}
* A [[van Emde Boas tree]] supports the ''minimum'', ''maximum'', ''insert'', ''delete'', ''search'', ''extract-min'', ''extract-max'', ''predecessor'' and ''successor]'' operations in ''O''(log log ''C'') time, but has a space cost for small queues of about ''O''(2<sup>''m''/2</sup>), where ''m'' is the number of bits in the priority value.<ref>P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In ''Proceedings of the 16th Annual Symposium on Foundations of Computer Science'', pages 75-84. IEEE Computer Society, 1975.</ref> The space can be reduced significantly with hashing.
* The [[Fusion tree]] by [[Michael Fredman|Fredman]] and [[Dan Willard|Willard]] implements the ''minimum'' operation in ''O''(1) time and ''insert'' and ''extract-min'' operations in <math>O(\log n / \log \log C)</math>time. However it is stated by the author that, "Our algorithms have theoretical interest only; The constant factors involved in the execution times preclude practicality."<ref>[[Michael Fredman|Michael L. Fredman]] and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. ''Journal of Computer and System Sciences'', 48(3):533-551, 1994</ref>

For applications that do many "[[Peek (data type operation)|peek]]" operations for every "extract-min" operation, the time complexity for peek actions can be reduced to ''O''(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. For insertion, this adds at most a constant cost, since the newly inserted element is compared only to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is typically cheaper than the deletion cost, so overall time complexity is not significantly impacted.

[[Monotone priority queue]]s are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min-heap) than any item previously extracted. This restriction is met by several practical applications of priority queues.

===Summary of running times===
{{Heap Running Times}}