Bounded Priority Queues ( b_priority_queue )

Definition

An instance Q of the parameterized data type b_priority_queue<I> is a collection of items (type b$\_$pq$\_$item). Every item contains a priority from a fixed interval [a..b] of integers (type int) and an information from an arbitrary type I. The number of items in Q is called the size of Q. If Q has size zero it is called the empty priority queue. We use < p, i > to denote a b_pq_item with priority p $\in$ [a..b] and information i.
Remark: Iteration over the elements of Q using iteration macros such as forall is not supported.

#include < LEDA/core/b_prio.h >

Creation

b_priority_queue<I>

Q(int a, int b)

creates an instance Q of type b_priority_queue<I> with key type [a..b] and initializes it with the empty priority queue.

Operations

b_pq_item	Q.insert(int key, const I& inf)
		adds a new item < key, inf > to Q and returns it. Precondition key $\in$ [a..b]
void	Q.decrease_key(b_pq_item it, int newkey)
		makes newkey the new priority of item it. Precondition it is an item in Q, newkey $\in$ [a..b] and newkey is not larger than prio(it).
void	Q.del_item(b_pq_item x)	deletes item it from Q. Precondition it is an item in Q.
int	Q.prio(b_pq_item x)	returns the priority of item i. Precondition it is an item in Q.
const I&	Q.inf(b_pq_item x)	returns the information of item i. Precondition it is an item in Q.
b_pq_item	Q.find_min()	returns an item with minimal priority (nil if Q is empty).
I	Q.del_min()	deletes the item it = Q.find_min() from Q and returns the information of it. Precondition Q is not empty.
void	Q.clear()	makes Q the empty bounded prioriy queue.
int	Q.size()	returns the size of Q.
bool	Q.empty()	returns true if Q is empty, false otherwise.
int	Q.lower_bound()	returns the lower bound of the priority interval [a..b].
int	Q.upper_bound()	returns the upper bound of the priority intervall [a..b].

Implementation

Bounded priority queues are implemented by arrays of linear lists. Operations insert, find_min, del_item, decrease_key, 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.