Monotone priority queue

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a monotone priority queue is a variant of the <a href="/facts/Priority_queue/1uXVo4Uf">priority queue</a> <a href="/facts/Abstract_data_type/BaVGSHNP">abstract data type</a> in which the priorities of extracted items are required to form a <a href="/facts/Monotonic_sequence/MjQK0YL2">monotonic sequence</a>. 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.: 128 
</p><p>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.
</p>

Monotone priority queue open-in-new

Monotone priority queue