Bei manchen Anwendungen von Prioritäts-Warteschlangen ist von vorneherein bekannt, dass alle jemals darin auftretenden Prioritäten p aus einem relativ kleinen Intervall [a..b] ganzer Zahlen stammen werden. Für diesen speziellen Fall einer Prioritäts-Warteschlange mit beschränkten, ganzzahligen Prioritäten (bounded integral priority queue) bietet LEDA über die Klasse b_priority_queue eine besonders effiziente Implementierung von Prioritäts-Warteschlangen an.

Im Konstruktor der Klasse müssen die Endpunkte a und b des Intervalls angegeben werden, aus dem die Prioritäten stammen. Diese Klasse hat nur einen Template-Parameter, nämlich den Typ der Information. Eine solche Prioritäts-Warteschlange BPQ mit Informationstyp I legt man also etwa durch

b_priority_queue<I> BPQ(a,b);

mit a und b vom Typ int an.

Diese Klasse folgt genauso wie die Klasse p_queue dem Item-Container-Konzept. Die Schnittstelle bietet im Wesentlichen dieselben Operationen an, unterscheidet sich jedoch in der Nomenklatur:

Warnung

Die Schnittstelle der Klasse b_priority_queue ändert oder vertauscht leider die Bezeichnungen der Schnittstelle p_queue an mehreren Stellen, was zu großer Verwirrung führen kann: Was bei p_queue als „Priorität“ bezeichnet wird, heißt hier „Information“. Was dort „Information“ ist, heißt hier „Schlüssel“. Demgemäß heißen die Methoden hier inf() bzw. decrease_inf() bzw. key(). Wir werden hier weiterhin konsequent von Paaren (p,i) aus Priorität und Information reden. Zudem vertauscht die Methode insert(i,p) von b_priority_queue die Reihenfolge der Argumente, und wenn der LEDA-Error-Handler eine Meldung der Form LEDA ERROR HANDLER         decrease_key: illegal key bringt, so sind damit dennoch die „Informationen“ von b_priority_queue gemeint, also die eigentlichen Prioritäten! Ungewöhnlicherweise heißt die einzubindende Header-Datei b_prio.h, und die Items sind vom Typ b_pq_item.

Als Anwendungsbeispiel wollen wir unser durch eine p_queue beschleunigtes Programm der Warteschlangensimulation nochmals für folgendes Szenario verbessern: Angenommen, es wurde festgestellt, dass sich nie mehr als 5 Reisende in einer Schlange vor einem Schalter befinden, weil kein Reisender Lust hat, sich an eine bereits derart lange Schlange anzustellen. Vielmehr verlässt ein Reisender sofort frustriert die Schalterhalle, wenn er feststellt, dass in jeder Schlange schon 5 Personen stehen. In diesem Szenario stammen alle auftretenden Prioritäten (d. h. alle Längen der Warteschlangen) aus dem Intervall [0..5]. Wir können daher statt einer p_queue auch eine b_priority_queue verwenden:

#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";
}

Die Ausgabe eines Beispiellaufes war:

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

Wir sehen, dass bei dieser Wahl von max_travellers_in_queue nur sehr wenige Reisende frustriert wieder von dannen ziehen.

Dieses Programm benötigt auf der Maschine des Autors nur 4,2 Sekunden, holt also gegenüber den 5,5 Sekunden der Version mit einer gewöhnlichen p_queue nochmals ca. 24% an Kaufzeitgewinn heraus! Das liegt daran, dass die Methoden insert(), find_min(), del_item(), decrease_inf(), key() und inf() alle Zeit O(1) benötigen; die Methode del_min() benötigt Zeit O(d), wobei d die Differenz der bisherigen kleinsten Priorität zur nächstkleineren Priorität ist.