Monotone priority queue

In computer science, a monotone priority queue is a variant of the priority queue abstract data type in which the priorities of extracted items are required to form a monotonic sequence. That is, for a priority queue in which each successively extracted item is the one with the minimum priority (a min-heap), the minimum priority should be monotonically increasing. Conversely for a max-heap the maximum priority should be monotonically decreasing. The assumption of monotonicity arises naturally in several applications of priority queues, and can be used as a simplifying assumption to speed up certain types of priority queues. A necessary and sufficient condition on a monotone priority queue is that one never attempts to add an element with lower priority than the most recently extracted one. Monotone priority queues arise naturally when arranging events in order of time, such as network timeouts or discrete event simulation. An event can cause some action to be scheduled at some time in the future, but (real or simulated) causality makes attempts to schedule actions in the past meaningless. In Dijkstra's algorithm for the shortest path problem, vertices of a given weighted graph are extracted in increasing order by their distance from the starting vertex, and a priority queue is used to determine the closest remaining vertex to the starting vertex. Therefore, in this application, the priority queue operations are monotonic. Similarly, in sweep line algorithms in computational geometry, events at which the sweep line crosses a point of interest are prioritized by the coordinate of the crossed point, and these events are extracted in monotonic ordering. A monotonic extraction order also occurs in the best-first version of branch and bound. Any priority queue that can handle non-monotone extraction operations can also handle monotone extractions, but some priority queues are specialized to work only for monotone extractions or work better when the extractions are monotone.