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.
^Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.
and 11 Related for: Monotone priority queue information
In computer science, a monotonepriorityqueue is a variant of the priorityqueue abstract data type in which the priorities of extracted items are required...
science, a priorityqueue is an abstract data type similar to a regular queue or stack abstract data type. Each element in a priorityqueue has an associated...
applications of priorityqueues such as Dijkstra's algorithm, the minimum priorities form a monotonic sequence, allowing a monotonepriorityqueue to be used...
radix heap is a data structure for realizing the operations of a monotonepriorityqueue. A set of elements to which a key is assigned can then be managed...
checking model of computation moderately exponential MODIFIND monotonepriorityqueue monotonically decreasing monotonically increasing Monte Carlo algorithm...
imminent and if the following verse "blessent mon cœur d'une langueur monotone" (wound my heart with a monotonous languor"), which was broadcast on 5...
search: traverses a graph in the order of likely importance using a priorityqueue Bidirectional search: find the shortest path from an initial vertex...
according to which any deterministic algorithm that tests a nontrivial monotone property of graphs, using queries that test whether pairs of vertices are...
Global Information