Global Information Lookup Global Information

Monotone priority queue information


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.

  1. ^ Mehlhorn, Kurt; Sanders, Peter (2008). "Priority queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer.

and 11 Related for: Monotone priority queue information

Request time (Page generated in 0.8801 seconds.)

Monotone priority queue

Last Update:

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...

Word Count : 752

Priority queue

Last Update:

computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated...

Word Count : 4656

Bucket queue

Last Update:

applications of priority queues such as Dijkstra's algorithm, the minimum priorities form a monotonic sequence, allowing a monotone priority queue to be used...

Word Count : 3312

Radix heap

Last Update:

radix heap is a data structure for realizing the operations of a monotone priority queue. A set of elements to which a key is assigned can then be managed...

Word Count : 619

List of terms relating to algorithms and data structures

Last Update:

checking model of computation moderately exponential MODIFIND monotone priority queue monotonically decreasing monotonically increasing Monte Carlo algorithm...

Word Count : 3134

Transdichotomous model

Last Update:

doi:10.1145/800076.802470, S2CID 12878381. Raman, Rajeev, "Priority Queues: Small, Monotone and Trans-dichotomous", Proceedings of the Fourth Annual European...

Word Count : 496

Predecessor problem

Last Update:

1236460, MR 2314255, S2CID 8175703. Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Fourth Annual European Symposium on...

Word Count : 988

French Resistance

Last Update:

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...

Word Count : 32998

Jean Vuillemin

Last Update:

according to which any deterministic algorithm that tests a nontrivial monotone property of graphs, using queries that test whether pairs of vertices are...

Word Count : 364

List of algorithms

Last Update:

search: traverses a graph in the order of likely importance using a priority queue Bidirectional search: find the shortest path from an initial vertex...

Word Count : 7835

Fusion tree

Last Update:

1016/S0304-3975(98)00172-8, MR 1678804. Raman, Rajeev (1996), "Priority queues: small, monotone and trans-dichotomous", Algorithms — ESA '96, Lecture Notes...

Word Count : 2434

PDF Search Engine © AllGlobal.net