the 'th, and updates , both in constant time. Extract-min deletes and returns one item from the list with index , then increments if needed until it again points to a non-empty list; this takes time in the worst case. These queues are useful for sorting the vertices of a graph by their degree. 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(2m/2), where m is the number of bits in the priority value. The space can be reduced significantly with hashing. The Fusion tree by Fredman and Willard implements the minimum operation in O(1) time and insert and extract-min operations in 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." For applications that do many "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 queues 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 Equivalence of priority queues and sorting algorithms Using a priority queue to sort The 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 algorithms, once the layer of abstraction provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms: Using a sorting algorithm to make a priority queue A sorting algorithm can also be used to implement a priority queue. Specifically, Thorup says: We present a general deterministic linear space reduction from priority queues