Editing Priority queue (section)

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