*Learning objectives*

The class `b_priority_queue` |

With some applications of priority queues it is known from
the start that all priorities p ever occurring therein will
originate from a relatively small interval [a..b] of integer
numbers. LEDA offers a particularly efficient implementation of * priority queues with bounded integral
priorities*, the class * b_priority_queue*.

The endpoints a and b of the interval that the priorities
originate from have to specified in the constructor of the
class. This class has only one template parameter, the type of the
information. Such a priority queue `BPQ`

with
information type `I`

and endpoints `a`

and `b`

can be constructed by

b_priority_queue<I> BPQ(a,b);

where `a`

and `b`

are of type `int`

.

Just as the class `p_queue`

,
also this class follows the item-container concept. The interface essentially offers the same
operations, though it differs in the nomenclature:

As a working example we want to improve our program for the queue
simulation, which we already accelerated by using a
`p_queue`

, for the following scenario:
Suppose it was noticed that it never happens that more than 5
travelers are standing in a queue in front of a desk, because no
traveler feels like standing in line in a queue already this
long. Rather, a traveler immediately exits the hall frustratedly
if he notices that every queue already contains 5 persons. In this
scenario, all occurring priorities (that is, all lengths of the
queues) originate from the interval [0..5]. We can therefore use a
`b_priority_queue`

instead of a
`p_queue`

:

#include <LEDA/queue.h> #include <LEDA/b_prio.h> #include <LEDA/list.h> #include <LEDA/array.h> #include <LEDA/random_variate.h> #include <iostream> #include "Traveller.h" using leda::queue; using leda::b_priority_queue; using leda::b_pq_item; using leda::array; using leda::random_variate; using leda::list; using std::cout; const int max_travellers_in_queue = 5; array< queue<Traveller*> > Queues(1,8); // Every queue knows the number of its travellers // There are now at most max_travellers_in_queue travellers in a queue b_priority_queue<int> BPQ(0,max_travellers_in_queue); array<b_pq_item> BPQITEM(1,8); // Every queue knows its item in BPQ list<int> Service_times; // needed for computation of variance const int mins_to_simulate = 60*24*7*52; // 1 full year int total_travellers = 0; int travellers_served = 0; int total_service_time = 0; int num_frustrated_travellers = 0; void output_statistics(); int main() { // initialize bounded priority queue BPQ: // there are 0 travellers in all 8 queues for(int i = 1; i <= 8; i++) BPQITEM[i] = BPQ.insert(i, 0); // WARNING! order of args reversed! // random variate of 'travellers per minute' array<int> weight(0,4); weight[0] = 1; weight[1] = 4; weight[2] = 6; weight[3] = 4; weight[4] = 1; // this gives 2 travellers per minute on the average random_variate R(weight); // for every minute of the time interval do the following for(int time = 0; time < mins_to_simulate; time++) { // some new travellers arrive int num_new_travellers = R.generate(); total_travellers += num_new_travellers; // queing the new travellers for(int i = 0; i < num_new_travellers; i++ ) { // find out queue with minimal length b_pq_item min_it = BPQ.find_min(); int min_queue = BPQ.key(min_it); // WARNING! 'inf' in p_queue int min_length = BPQ.inf(min_it); // WARNING! 'prio' in p_queue // has this queue already max_travellers_in_queue travellers? if(min_length == max_travellers_in_queue) { // the remaining new travellers // leave the system immediately in frustration num_frustrated_travellers += (num_new_travellers - i); break; } Traveller* T = new Traveller(time); // traveller T goes to the queue with minimal length Queues[min_queue].append(T); // this queue has now one more traveller // BUT: one cannot increase priority! // use the following trick: delete and insert with new priority BPQ.del_min(); // WARNING! order of args reversed! BPQITEM[min_queue] = BPQ.insert(min_queue, min_length + 1); } // travellers at the front of the queues get served for(int i = 1; i <= 8; i++) if(!Queues[i].empty()) { Traveller* T = Queues[i].top(); if(T->dec_time_to_serve() == 0) { // T leaves the system Queues[i].pop(); // queue i has now one less traveller int old_p = BPQ.inf(BPQITEM[i]); // WARNING: 'prio' in p_queue BPQ.decrease_inf(BPQITEM[i], old_p - 1 ); travellers_served++; int time_used = time - T->get_arrival_time(); total_service_time += time_used; Service_times.append(time_used); delete T; } } } output_statistics(); } void output_statistics() { double mean = total_service_time / (double)travellers_served; // compute standard deviation int time; double sum; forall(time, Service_times) sum += (time - mean) * (time - mean); double variance = sum / (Service_times.size()-1); double stddev = sqrt(variance); cout << "Total number of travellers arrived = " << total_travellers << "\n"; cout << "Total number of travellers served = " << travellers_served << "\n"; cout << "Total number of frustrated travellers not served = " << num_frustrated_travellers << "\n"; cout << "Total service time = " << total_service_time << "\n"; cout << "Service time per traveller = " << mean << "\n"; cout << "Standard deviation = " << stddev << "\n"; }

The output of an example run was:

Total number of travellers arrived = 1048537 Total number of travellers served = 1048286 Total number of frustrated travellers not served = 241 Total service time = 5637477 Service time per traveller = 5.3778 Standard deviation = 3.42378

We see that with this value of
`max_travellers_in_queue`

only very few travelers move
away frustratedly.

This program takes only 4.2 seconds on the author's
machine. This means a running time saving of 5.5 seconds or 24%
compared with the version that uses an ordinary
`p_queue`

! The reason for this speed-up is that
the methods `insert()`

,
`find_min()`

, `del_item()`

,
`decrease_inf()`

, `key()`

,
and `inf()`

all take time O(1); the method
`del_min()`

takes time O(d), with d being the
difference between the (currently) lowest priority and the second
lowest priority.

For the implementation of
`b_priority_queue`

, see Exercise 45.

Compared with a `p_queue`

, the use of
a `b_priority_queue`

is primarily
worthwhile if the interval [a..b] of the priorities actually
occurring is small. If this interval is very large, then
`b_priority_queue`

should not be used,
because the storage required by the data structure grows with
the length b-a of the interval: It is O(b-a+n), with n being the
number of pairs (p,i) stored in the structure.

More about the class
`b_priority_queue`

can be found on the
corresponding manual page.