Monotone priority queue

In computer science, a monotone priority queue is a variant of the priority queue/heap data structure. It offers insert and extract-min operations (or extract-max; this article assumes min-priority queues, without loss of generality), like an ordinary priority queue, but imposes the restriction that a key (item) may only be inserted if its priority is greater than that of the last key extracted from the queue. This entails that the sequence of keys extracted from the queue form a monotonically increasing sequence.[1]:128 This restriction is met by several applications, including discrete event simulation and the best-first version of branch and bound.[1]:128

Specialized monotone PQ data structures can be used to obtain asymptotically better running times for algorithms using them, compared to standard priority queues. For example, in graphs with integer edge costs, these structures can be used to speed up Dijkstra's algorithm for shortest-path finding[2] (for arbitrary edge costs, it is unknown whether a speedup can be achieved[1]:201).

References

  1. 1 2 3 Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer.
  2. ↑ Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (1999). "Buckets, heaps, lists, and monotone priority queues". SIAM J. Computing 28 (4): 1326–1346.

Further reading

This article is issued from Wikipedia - version of the Friday, November 27, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.