Monotone priority queue: Difference between revisions
→Applications: Expanded on time-based usage, moved to top, as I think it's the simplest example. |
Add details to refs |
||
Line 1: | Line 1: | ||
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.<ref name="mehlhorn">{{cite book |
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.<ref name="mehlhorn">{{cite book |
||
| last1=Mehlhorn | first1=Kurt | author1-link=Kurt Mehlhorn |
|||
| first2=Peter | last2=Sanders | author2-link=Peter Sanders (computer scientist) |
|||
| title=Algorithms and Data Structures: The Basic Toolbox |
|||
| chapter=Priority queues |
|||
| publisher=Springer |
|||
| year=2008 |
|||
| url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/ |
|||
| chapter-url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/PriorityQueues.pdf#page=2 |
|||
}}</ref>{{rp|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== |
==Applications== |
||
Line 12: | Line 23: | ||
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. |
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 (computing)|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). |
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 (computing)|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.<ref>{{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|authorlink=Steven Skiena|publisher=Springer|year=1998|isbn= |
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.<ref>{{citation |
||
| title=The Algorithm Design Manual |
|||
| first=Steven S. | last=Skiena | authorlink=Steven Skiena |
|||
| publisher=Springer |
|||
| year=1998 |
|||
| isbn=978-0-387-94860-7 |
|||
| page=181 |
|||
| url=https://books.google.com/books/about/The_Algorithm_Design_Manual.html?id=TrXd-gxPhVYC&pg=PA181 |
|||
}}.</ref> |
|||
{{harvtxt|Cherkassky|Goldberg|Silverstein|1999}} describe a more complicated scheme called a [[ |
{{harvtxt|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 {{math|0}} to a parameter {{math|C}}. The hot queue uses constant time per insertion or decrease-priority operation and [[amortized time]] <math>O((\log C)^{1/3}(\log\log C)^{1/2})</math> per extract-min operation.<ref>{{citation |
||
| last1 = Cherkassky | first1 = Boris V. |
| last1 = Cherkassky | first1 = Boris V. |
||
| last2 = Goldberg | first2 = Andrew V. | author2-link = Andrew V. Goldberg |
| last2 = Goldberg | first2 = Andrew V. | author2-link = Andrew V. Goldberg |
||
| last3 = Silverstein | first3 = Craig |
| last3 = Silverstein | first3 = Craig |
||
⚫ | |||
| issue = 4 |
|||
| journal = [[SIAM Journal on Computing]] |
| journal = [[SIAM Journal on Computing]] |
||
⚫ | |||
| date = August 1999 |
|||
| mr = 1681014 |
| mr = 1681014 |
||
⚫ | |||
| title = Buckets, heaps, lists, and monotone priority queues |
| title = Buckets, heaps, lists, and monotone priority queues |
||
⚫ | |||
| volume = 28 |
|||
| citeseerx = 10.1.1.49.8244}}.</ref> Another related structure of {{harvtxt|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 {{mvar|n}} items taking amortized time <math>O(\sqrt{\log n\log\log n})</math>.<ref>{{citation |
|||
| last = Raman | first = Rajeev |
| last = Raman | first = Rajeev |
||
⚫ | |||
| contribution = Priority queues: small, monotone and trans-dichotomous |
| contribution = Priority queues: small, monotone and trans-dichotomous |
||
| contribution-url = https://pdfs.semanticscholar.org/d6bd/b9bf6e2338ae5424404b5117eae4c5bdbcb5.pdf |
|||
| doi = 10.1007/3-540-61680-2_51 |
| doi = 10.1007/3-540-61680-2_51 |
||
| mr = 1469229 |
| mr = 1469229 |
||
| pages = 121–137 |
| pages = 121–137 |
||
| publisher = Springer |
| publisher = Springer | location = Berlin |
||
| series = Lecture Notes in |
| series = Lecture Notes in Computer Science |
||
⚫ | |||
| volume = 1136 |
| volume = 1136 |
||
| year = 1996}}.</ref> |
| year = 1996}}.</ref> |
Revision as of 01:06, 1 June 2018
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 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 .[4] These results lead to a corresponding speedup in Dijkstra's algorithm for graphs with integer edge weights.
References
- ^ a b Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.
- ^ Skiena, Steven S. (1998), The Algorithm Design Manual, Springer, p. 181, ISBN 978-0-387-94860-7.
- ^ 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.
- ^ Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous" (PDF), Algorithms—ESA '96 (Barcelona), Lecture Notes in Computer Science, vol. 1136, Berlin: Springer, pp. 121–137, doi:10.1007/3-540-61680-2_51, MR 1469229.