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:

Warning

Unfortunately, the interface of the class b_priority_queue changes or swaps the names of the interface of the class p_queue in several places, which can lead to big confusion: The “priority” of a p_queue is called an “information” in a b_priority_queue, the “information” is called a “key”. Accordingly, the methods are called inf(), decrease_inf(), and key(). To stay consistent, we will continue talking of pairs (p,i) consisting of a priority and an information. Moreover, the method insert(i,p) of b_priority_queue swaps the order of the arguments, and when the LEDA error handler outputs a message saying LEDA ERROR HANDLER         decrease_key: illegal key this nevertheless denotes the “information” of b_priority_queue, that is, the actual priority! There are two further unusual namings: The header file that has to be included is called b_prio.h, and the items are of type b_pq_item.

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.