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. ^{[1] :128}

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.

Applications

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. ^{[1] :128}

Data structures

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. For instance, the bucket queue is a simple priority queue data structure consisting of an array indexed by priority, where each array cell contains a bucket of items with that priority. An extract-min operation performs a sequential search for the first non-empty bucket and chooses an arbitrary item in that bucket. For non-monotone extractions, each extract-min operation takes time (in the worst case) proportional to the array length (the number of distinct priorities). However, when used as a monotone priority queue, the search for the next non-empty bucket can begin at the priority of the most recent previous extract-min operation rather than at the start of the array. This optimization causes the total time for a sequence of operations to be proportional to the sum of the number of operations and the length of the array, rather than (as in the non-monotonic case) the product of these two quantities. ^[2]

Cherkassky, Goldberg & Silverstein (1999) describe a more complicated scheme called a Heap-on-top (HOT) queue for monotone priority queues with integer priorities, based on multilevel bucketing together with a conventional heap priority queue. Using this method they obtain a structure that can maintain items with integer priorities in a range from 0 to a parameter C. The hot queue uses constant time per insertion or decrease-priority operation and amortized time ${\displaystyle O((\log C)^{1/3}(\log \log C)^{1/2})}$ per extract-min operation. ^[3] Another related structure of Raman (1996) allows the priorities to be machine integers, and again allows constant-time insertion and decrease-priority operations, with extract-min operations on a priority queue of n items taking amortized time ${\displaystyle O({\sqrt {\log n\log \log n}})}$. ^[4] These results lead to a corresponding speedup in Dijkstra's algorithm for graphs with integer edge weights.

References

1. Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.
2. Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN   978-0-387-94860-7 .
3. Cherkassky, Boris V.; Goldberg, Andrew V.; Silverstein, Craig (August 1999), "Buckets, heaps, lists, and monotone priority queues", SIAM Journal on Computing , 28 (4): 1326–1346 (electronic), CiteSeerX   10.1.1.49.8244 , doi:10.1137/S0097539796313490, MR   1681014 .
4. Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous" (PDF), Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR   1469229 .