Definition
An instance Q of the parameterized data type b_priority_queue<K> is a priority_queue (cf. section Priority Queues) whose information type is a fixed interval [a..b] of integers.
#include < LEDA/b _prio.h >
Creation
| b_priority_queue<K> | Q(int a, int b) | creates an instance Q of type b_priority_queue<K> with information type [a..b] and initializes it with the empty priority queue. |
Operations
See section Priority Queues.
Implementation
Bounded priority queues are implemented by arrays of linear lists. Operations insert, find_min, del_item, decrease_inf, key, inf, and empty take time O(1), del_min (= del_item for the minimal element) takes time O(d ), where d is the distance of the minimal element to the next bigger element in the queue (= O(b - a) in the worst case). clear takes time O(b - a + n) and the space requirement is O(b - a + n), where n is the current size of the queue.