Next: Lossless Compression
Up: Priority Queues
Previous: Priority Queues ( p_queue
Contents
Index
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
bpqitem
). 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 [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 [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 [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.
Next: Lossless Compression
Up: Priority Queues
Previous: Priority Queues ( p_queue
Contents
Index
Christian Uhrig
20170407