4.1. Prioritäts-Warteschlangen mit unbeschränkten Prioritäten (Klasse p_queue)

Lernziele

Die Klasse p_queue

Die Klasse p_queue ist LEDAs Typ für Prioritäts-Warteschlangen mit unbeschränkten Prioritäten. Eine solche Warteschlange enthält Paare (p,i) bestehend aus einer Priorität p und einer Information i. Jeder Information i ist dabei eine Priorität p zugeordnet. Der Typ P der Prioritäten muss ein linear geordneter sein. Die Paare liegen in aufsteigender Priorität geordnet in der Warteschlange. Jede Priorität p des Typs P darf dabei verwendet werden; die Prioritäten dürfen also unbeschränkt auftreten. Für die Informationen darf ein beliebiger Typ I verwendet werden. Eine Prioritäts-Warteschlange mit Prioritätstyp P und Informationstyp I wird erzeugt durch

p_queue<P,I> PQ;

Diese Klasse folgt ebenfalls dem Item-Container-Konzept: Auf die Paare selbst kann nur über Items des Typs pq_item zugegriffen werden. Ein solches Item wird geliefert, wenn ein Paar (p,i) in die Prioritäts-Warteschlange aufgenommen wird, oder wenn explizit nach einem Paar mit kleinster Priorität gefragt wird. Dies geschieht mittels der Methoden

pq_item it = PQ.insert(p,i);

bzw.

pq_item it = PQ.find_min();

Gelöscht werden kann ein Paar mit kleinster Priorität durch

P p = PQ.del_min();

Diese Methode liefert gleichzeitig die Priorität dieses Paares zurück.

Ein bestimmtes Paar kann ausgehend von einem pq_item, das auf dieses Paar verweist, gelöscht werden:

PQ.del_item(it);

Ebenfalls ausgehend von einem Item können die Priorität und die Information des dadurch referenzierten Paares (p,i) erfragt werden:

P p = PQ.prio(it);
I i = PQ.inf(it);

Die Information kann, wiederum ausgehend von einem Item, beliebig abgeändert werden:

PQ.change_inf(it, new_i);

Die Priorität p dagegen kann nur vermindert werden:

PQ.decrease_p(it, new_p); // new_p <= old_p !

Dies liegt an der besonders effizienten Implementierung der Prioritäts-Warteschlangen über so genannte Fibonacci-Heaps; in dieser Einschränkung der Schnittstelle folgt LEDA auch der klassischen Definition einer Prioritäts-Warteschlange.

[Warning] Warnung

Diese Datenstuktur darf nicht mit einem assoziativen Containertyp verwechselt werden, bei dem über einen Schlüssel auf den zugehörigen Wert zugegriffen wird. Es ist nicht möglich, anhand einer vorgegebenen Priorität die Information oder besser die Informationen zu suchen, die diese Priorität haben. Es ist auch umgekehrt nicht möglich, von einer Information ausgehend zu fragen, ob und mit welcher Priorität diese in der Warteschlange vorkommt. Und schließlich bietet diese Struktur auch keine Möglichkeit an, über die in ihr enthaltenen Paare zu iterieren. Will man dies tun, so muss man die beim Einfügen der Paare zurückgelieferten Items selbst aufsammeln und verwalten, etwa in einer Liste.

Durchaus können Paare mit gleicher Priorität und/oder gleicher Information in einer p_queue enthalten sein. Wenn zwei Paare (p,i) und (p, i') mit gleicher Priorität in die Warteschlange aufgenommen werden, dann gibt es keine Vereinbarung darüber, welches der Paare als erstes wieder entnommen wird; dieses Paar wird gewissermaßen zufällig bestimmt. Insbesondere muss daher Folgendes beachtet werden:

[Important] Wichtig

Eine p_queue garantiert nicht, dass von zwei eingefügten Paaren (p,i) und (p,i') mit gleicher Priorität p dasjenige als erstes wieder herausgezogen wird, das als erstes aufgenommen wurde. In diesem Sinne wird keine Stabilität der Sortierung garantiert. Möchte man dies unbedingt sicherstellen, so muss man diese Eintrittszeitpunkte in die Priorität einmodellieren, etwa indem man als Prioritäts-Typ einen Verbundtyp benutzt, der neben der ursprünglichen Priorität p auch noch einen Zeitstempel t und eine darauf angepasste Version von compare() enthält, die den Stempel t beim Vergleich mit einbezieht.

Ein Anwendungsbeispiel: Huffman-Kodierung

Die Huffman-Kodierung ist ein Kompressionsverfahren, das besonders auf Dateien effizient ist, die textuelle, natürlichsprachliche Daten beinhalten. Damit sind Dateien gemeint, die aus bestimmten Zeichen eines Zeichenvorrats bestehen, von denen manche mit großer Häufigkeit vorkommen (wie im Deutschen das Zeichen „e“), andere nur mit geringer (wie im Deutschen das Zeichen „x“). Auf solchen Dateien erzielt die Huffman-Kodierung sehr gute Kompressionsraten.

Wie arbeitet dieses Verfahren? Angenommen, wir haben folgenden Text, der aus 100 Zeichen besteht, die darin mit unterschiedlicher Häufigkeit vorkommen:

caaabacfaabbebaaacbabdaaceadcccaaaaaaacabaaafbcaad
bacdaaaacdccacbaafbcfaaccaaaadadcdcddcabeaeefabfaa

Wie viele Bits brauchen wir, um diesen Text zu kodieren? Wie wir sehen, tauchen darin nur die Zeichen a, b, c, d, e und f auf. Die einfachste Möglichkeit der Kodierung ist es, jedes Zeichen mit derselben, fixen Anzahl von Bits darzustellen. Dies wird als Kodierung mit fixer Länge (fixed-length coding) bezeichnet. Da insgesamt nur 6 Zeichen auftreten, genügen hierfür 3 Bits pro Zeichen. (Es ist 2^3=8, d. h., wir könnten damit sogar 8 verschiedene Zeichen darstellen.) Tabelle 4.1 zeigt eine mögliche Kodierung mit fixer Länge. Damit benötigen wir insgesamt 100·3 = 300 Bits zur Kodierung des gesamten Textes.

Können wir durch eine andere Kodierung mit weniger Bits auskommen? Wir machen folgende Beobachtung: Das Zeichen a taucht mit Abstand am häufigsten im Text auf, nämlich 46 Mal. Dagegen taucht e nur 5 Mal auf. Es riecht doch daher nach Verschwendung, wenn wir für jedes a genauso viele Bits vorsehen wir für jedes e. Wir sollten dagegen a mit möglichst wenig Bits kodieren, z. B. nur mit einem einzigen, etwa der 0, und dafür in Kauf nehmen, dass die Kodierung von selten auftretenden Zeichen wie dem e mehr als 3 Bits benötigt. Eine solche Kodierung, bei der sich die Anzahl der Bits von Zeichen zu Zeichen unterscheiden kann, wird als Kodierung mit variabler Länge (variable-length coding) bezeichnet. Tabelle 4.1 zeigt eine solche Kodierung mit variabler Länge. Hier benötigen wir nur 46·1 + 13·3 + 20·3 + 10·3 + 5·4 + 6·4 = 219 Bits, um den Text zu kodieren, erzielen also eine Kompressionsrate von 219/300 = 73%. Die Kodierung mit variabler Länge ist also um 27% kürzer als die mit fixer Länge.

Tabelle 4.1. Der Huffman-Code

  a b c d e f
Häufigkeit 46 13 20 10 5 6
Kodierung mit fixer Länge 000 001 010 011 100 101
Huffman-Kodierung 0 110 111 100 1010 1011

Die in Tabelle 4.1 vorgestellte Kodierung mit variabler Länge ist eine so genannte präfix-freie Kodierung (prefix-free code). Das bedeutet, dass die Kodierung eines Zeichens niemals Präfix der Kodierung eines anderen Zeichens ist, was die Kodierung und Dekodierung eines Gesamttextes einfach macht; s. hierzu auch Übung 41. Eine solche Kodierung kann immer als binärer Baum dargestellt werden. Jedes Blatt entspricht einem Zeichen des Zeichenvorrats. Jede Kante ist mit 0 bzw. 1 beschriftet. Die Kodierung eines Zeichens ergibt sich aus der Konkatenation aller Beschriftungen auf dem Pfad von der Wurzel bis zu dem entsprechenden Blatt. Abbildung 4.1 zeigt den Baum, der zu obiger präfix-freier Kodierung gehört.

Abbildung 4.1. Huffman-Kodierung als vollständiger binärer Baum

Huffman-Kodierung als vollständiger binärer Baum

Ein Baum, der der Huffman-Kodierung aus Tabelle 4.1 entspricht. Jedes Blatt entspricht einem Zeichen und enthält die Häufigkeit, mit der dieses Zeichen vorkommt. Jeder Knoten enthält als Beschriftung die Summe der Beschriftungen seiner Kinder. Das Kind mit der kleineren Beschriftung ist immer das linke Kind. Die Kante zu diesem Kind ist mit 0 beschriftet, die Kante zum rechten mit 1. Die Huffman-Kodierung eines Zeichens entspricht der Folge der Kantenbeschriftungen auf dem Pfad von der Wurzel bis zu diesem Zeichen.

Eine optimale präfix-freie Kodierung (für eine vorgegebene Häufigkeitsverteilung von Einzelzeichen) ist eine präfix-freie Kodierung, die von allen möglichen präfix-freien Kodierungen die beste Kompressionsrate erzielt. Die Kodierung aus Tabelle 4.1 und der zugehörige Baum aus Abbildung 4.1 stellen eine optimale präfix-freie Kodierung für den ursprünglichen Text dar; sie wurden durch ein Verfahren erzeugt, das eine solche optimale präfix-freie Kodierung berechnet.

Dieses Verfahren wurde von David Huffman erfunden und wird heute nach ihm als Huffman-Kodierung bezeichnet. Es baut den Kodierungs-Baum sukzessive auf. Die Grundidee dabei ist die folgende: Die Blätter des Baumes entsprechen den zu kodierenden Zeichen. Die Zeichen, die am seltensten auftreten, sollten die längste Kodierung erhalten, also die längsten Pfade von der Wurzel aus aufweisen. Daher werden zunächst alle Zeichen gemäß ihrer Häufigkeit in eine Prioritäts-Warteschlange eingeordnet, und die beiden Zeichen mit der geringsten Priorität (also der geringsten Häufigkeit) werden daraus entnommen. Für diese beiden Zeichen steht nun das letzte Bit ihrer Kodierung, also die Beschriftung der letzten Kante auf dem Pfad von der Wurzel aus, bereits fest: Das seltenste Zeichen erhält eine 1, das zweitseltenste eine 0. Sie erhalten im zu erzeugenden Baum einen gemeinsamen Vaterknoten, dessen Priorität sich aus der Summe der Häufigkeiten (Prioritäten) der beiden Kinder ergibt. Dieser Vaterknoten wird nun selbst in die Prioritäts-Warteschlange eingeordnet, und das Verfahren geht in die nächste Iteration: Es zieht sich die beiden Knoten mit geringster Priorität aus der Warteschlange, ordnet sie unter einen gemeinsamen Vaterknoten ein, der die Summe der Prioritäten der beiden Kinder als Priorität enthält usw. Abbildung 4.2 zeigt diesen Prozess für die Verteilung aus Tabelle 4.1. Wir wollen hier nicht begründen, warum das Verfahren immer eine optimale präfix-freie Kodierung liefert, und verweisen diesbezüglich auf weiterführende Literatur (z. B. auf die Darstellung in [2], der wir hier insgesamt folgen).

Abbildung 4.2. Konstruktion des Huffman-Codes

Konstruktion des Huffman-Codes

Eine Prioritäts-Warteschlange wird mit den zu kodierenden Zeichen gefüllt; die Priorität entspricht dabei der Häufigkeit des Zeichens. Jedes Zeichen ist Blatt eines zu konstruierenden Baumes. In jedem Schritt werden die beiden Teilbäume mit geringster Priorität vereinigt. Der linke Teilbaum ist dabei der mit der kleineren Priorität; die Kante zu ihm wird mit 0 beschriftet, die Kante zum rechten Teilbaum mit 1. Die Priorität des neu entstehenden Teilbaumes ist die Summe der Prioritäten der beiden vereinigten Teilbäume. Das Verfahren endet, wenn in der Prioritäts-Warteschlange nur noch die gemeinsame Wurzel enthalten ist. Die Kodierung eines Zeichens ergibt sich als Folge der Kantenbeschriftungen auf dem Weg von der Wurzel zum entsprechenden Blatt.

Das folgende Programm benutzt eine p_queue, um die in Huffmans Algorithmus auftretende Prioritäts-Warteschlange zu realisieren. Es liest zunächst die Standardeingabe aus und zählt in einem d_array mit, welches Zeichen wie oft darin vorkommt. Ausgehend von dieser Häufigkeitsverteilung baut es sich den Baum explizit auf. Dabei verwendet es eine Struktur huffman_node, um die im Baum auftretenden Knoten zu implementieren. Diese Struktur speichert einen Verweis auf den jeweiligen Vaterknoten, die Priorität des Knotens und die Information, ob dieser Knoten ein linkes oder ein rechtes Kind seines Vaters ist. Jedes Zeichen muss am Ende das zu ihm gehörige Blatt des Baumes kennen, um von dort aus den Pfad zur Wurzel hinauf erklimmen zu können. Daher merkt sich das Programm in einem zusätzlichen d_array zu jedem Zeichen das zugehörige Blatt.

Filename: HuffmanCode.C
#include <LEDA/d_array.h>
#include <LEDA/p_queue.h>
#include <LEDA/string.h>

using leda::d_array;
using leda::p_queue;
using leda::string;
using std::cin;
using std::cout;

class huffman_node {
public:
  huffman_node *parent;
  int priority;
  bool is_left_child;
  // set parent to nil when constructing a new huffman_node
  huffman_node() : parent(nil) {};
};


int main()
{
  d_array<char,int> H;
  char c;
  
  // read all characters from stdin and count their frequency
  while(cin >> c) H[c]++;

  p_queue<int, huffman_node*> PQ;
  d_array<char, huffman_node*> leaf_belonging_to_char;

  // for every character insert a huffman node into the priority queue
  // this node is a leaf of the tree to be constructed
  forall_defined(c,H) {
    cout << c << ": " << H[c] << std::endl;
    huffman_node *new_leaf = new huffman_node;
    new_leaf->priority = H[c];
    PQ.insert(H[c], new_leaf);
    leaf_belonging_to_char[c] = new_leaf;
  }

  // construct the Huffman code
  cout << "Constructing the Huffman code for all read characters.\n";

  while(PQ.size() > 1) {

    // extract two children with minimal priority
    huffman_node *left_child = PQ.inf(PQ.find_min());
    PQ.del_min();
    huffman_node *right_child = PQ.inf(PQ.find_min());
    PQ.del_min();

    // construct new parent node
    huffman_node *new_parent = new huffman_node;
    left_child->parent = right_child->parent = new_parent;
    left_child->is_left_child = true;
    right_child->is_left_child = false;
    new_parent->priority = left_child->priority + right_child->priority;

    // insert new parent into priority queue
    PQ.insert(new_parent->priority, new_parent);
    
    // control output
    cout << "New parent created with priority ";
    cout << new_parent->priority << " = ";
    cout << left_child->priority << " + " << right_child->priority << "\n";
  }

  cout << "The Huffman codes are:\n";

  // output the codes: climb from all leaves to the root
  forall_defined(c, H) {
    cout << c << ": ";
    huffman_node *climber = leaf_belonging_to_char[c];
    string huffman_code; // collect 0s and 1s on the path to the root
    while(climber->parent != nil) { // do nothing for the root
      if(climber->is_left_child)
        huffman_code = "0" + huffman_code;
      else
        huffman_code = "1" + huffman_code;
      climber = climber->parent;
    }
    cout << huffman_code << std::endl;
  }
}

Angesetzt auf obigen Text aus 100 Zeichen gibt das Programm Folgendes aus:

a: 46
b: 13
c: 20
d: 10
e: 5
f: 6
Constructing the Huffman code for all read characters.
New parent created with priority 11 = 5 + 6
New parent created with priority 21 = 10 + 11
New parent created with priority 33 = 13 + 20
New parent created with priority 54 = 21 + 33
New parent created with priority 100 = 46 + 54
The Huffman codes are:
a: 0
b: 110
c: 111
d: 100
e: 1010
f: 1011

Die Hauptschleife fragt mittels der Methode

PQ.size();

ab, ob noch mindestens 2 Knoten in der Prioritäts-Warteschlange enthalten sind. Am Schluss besteht die Warteschlange nur noch aus dem Wurzelknoten, der nicht mehr weiter bearbeitet werden muss.

Ein komplexeres Anwendungsbeispiel

Im Programm zur Simulation der alten Warteschlangenpolitik am Saarbrücker Hauptbahnhof haben wir einen Tipp zur Beschleunigung hinterlassen: Jedesmal, wenn sich ein Reisender an eine der 8 Warteschlangen anstellt oder eine von diesen verlässt, ruft die Simulation die Funktion compute_shortest_queue() auf; sie muss zu jedem Zeitpunkt wissen, welches die gerade kürzeste Warteschlange ist, damit sie den nächsten zu bedienenden Reisenden an eben diese anfügen kann. Die Implementierung von compute_shortest_queue() ist primitiv: Sie läuft mit einer for-Schleife über alle 8 Warteschlangen und bestimmt diejenige, die die kleinste Länge hat.

Klüger wäre es doch, wenn wir einfach immer wüssten, welches die gerade kürzeste Schlange ist! Dazu müssten wir eine Datenstruktur haben, in der die Nummern der Warteschlangen gespeichert werden können, nach der Anzahl ihrer Elemente (also der Anzahl der darin enthaltenen Reisenden) geordnet, und aus der wir immer die Nummer mit der gerade geringsten Anzahl extrahieren können. Eine solche Datenstruktur haben wir aber gerade kennen gelernt: p_queue!

Inwiefern ist die Verwendung einer zusätzlichen p_queue wirklich klüger? Zunächst einmal verkompliziert sie nämlich den Programmtext, wie wir gleich sehen werden. Nun ist aber p_queue eine Datenstruktur, deren Such-, Einfüge- und Löschoperationen besonders effizient implementiert sind: Ein Aufruf von insert(), del_item() oder del_min() benötigt bei n in der Struktur gespeicherten Paaren nur Zeit O(log(n)); die anderen Operation benötigen sogar immer nur Zeit O(1). Das heißt mit anderen Worten, dass sich in obiger Situation die kürzeste Warteschlange sehr schnell finden lässt.

Wie führen also eine zusätzliche p_queue<int,int> PQ ein, in der Paare (n,q) gespeichert sind. n ist dabei die augenblickliche Anzahl der Reisenden in der Warteschlange mit der Nummer q. n hat dabei also die Rolle der Priorität, nach der die Paare in der Prioritäts-Warteschlange PQ geordnet sind.

Was müssen wir tun, wenn wir die Nummer q der kürzesten Warteschlange bestimmt haben? In dem Fall, dass ein Reisender diese Schlange verlässt, muss das zugehörige n um 1 vermindert werden. Das geht sehr schnell, nämlich in Zeit O(1), durch die Methode decrease_p. Dazu muss aber die Warteschlange mit der Nummer q ein Item kennen, das auf das entsprechende Paar (n,q) in der Prioritäts-Warteschlange PQ verweist. Daher müssen wir uns in einem zusätzlichen Array array<pq_item> PQITEM zu jeder Warteschlange ein zugehöriges Item merken. Wir sehen, wie der Quellcode immer komplexer wird - diese Art von Indirektionen und Referenzierungen über verschiedene Strukturen hinweg ist typisch für das fortgeschrittene Modellieren und Programmieren mit den Datenstrukturen von LEDA.

In dem Fall, dass ein neu hinzugekommener Reisender sich an die Warteschlange q anstellt, stossen wir auf ein Problem: Wir können die zugehörige Anzahl n nicht erhöhen, weil sich Prioritäten in Prioritäts-Warteschlangen nur vermindern lassen. Hier behelfen wir uns mit einem Trick:

[Tip] Tipp

Um die Priorität eines Paares (p,i) in einer Prioritäts-Warteschlange zu erhöhen, was über die Schnittstelle nicht direkt möglich ist, kann das Paar entfernt und i mit der neuen Priorität p' in einem neuen Paar (p',i) wieder eingefügt werden.

Hier ist die verbesserte Version des Programmes aus Abschnitt 2.7.1:

Filename: QueueExperiment1PriorityQueue.C
#include <LEDA/queue.h>
#include <LEDA/p_queue.h>
#include <LEDA/list.h>
#include <LEDA/array.h>
#include <LEDA/random_variate.h>
#include <iostream>
#include "Traveller.h"

using leda::queue;
using leda::p_queue;
using leda::pq_item;
using leda::array;
using leda::random_variate;
using leda::list;
using std::cout;

array< queue<Traveller*> > Queues(1,8);
p_queue<int, int> PQ; // Every queue knows the number of its travellers
array<pq_item> PQITEM(1,8); // Every queue knows its item in PQ

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;

//void compute_shortest_queue(); not needed any more!
void output_statistics();

int main()
{

  // initialize priority queue PQ: there are 0 travellers in all 8 queues
  for(int i = 1; i <= 8; i++)
    PQITEM[i] = PQ.insert(0,i);

  // 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++ ) {
      Traveller* T = new Traveller(time);
      // find out queue with minimal length
      pq_item min_it = PQ.find_min();
      int min_queue = PQ.inf(min_it);
      int min_length = PQ.prio(min_it);
      // 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
      PQ.del_min();
      PQITEM[min_queue] = PQ.insert(min_length + 1, min_queue);
    }

    
    // 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 = PQ.prio(PQITEM[i]);
          PQ.decrease_p(PQITEM[i], old_p - 1);
          travellers_served++;
          //compute_shortest_queue(); not needed any more!
          int time_used = time - T->get_arrival_time();
          total_service_time += time_used;
          Service_times.append(time_used);
          delete T;
        }
      }
  }

  output_statistics();
}


// update min_queue: not needed any more!
/*
void compute_shortest_queue() {
  for(int j = 1; j <= 8; j++)
    if(Queues[j].size() < Queues[min_queue].size())
      min_queue = j;
}
*/


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 service time = " << total_service_time << "\n";
  cout << "Service time per traveller = " << mean << "\n";
  cout << "Standard deviation = " << stddev << "\n";
}

Unser Gebrauch der Prioritäts-Warteschlange ist hier ein wenig unkonventionell: In den meisten Anwendungen werden decrease_p() und del_min() wesentlich öfter aufgerufen als insert().

Aber die zusätzliche Prioritäts-Warteschlange zahlt sich aus: Auf der Maschine des Autors benötigt die ursprüngliche Simulation 8,1 Sekunden, die beschleunigte dagegen nur 5,5. Das bedeutet eine Zeitersparnis von 32%, was recht erstaunlich ist, da das ursprünglich verwendete compute_shortest_queue() pro Aufruf nur 8 Iterationen mit wenigen, einfachen Operationen durchführt! Das macht deutlich, wie schnell die Implementierung von p_queue ist.

Implementierung und Tipps

Die Klasse p_queue ist durch Fibonacci-Heaps implementiert. Befinden sich n Paare darin, so benötigt sie O(n) viel Speicherplatz. Die Methoden insert(), del_item() und del_min() benötigen Zeit O(log n). Die Methode clear(), die alle Paare aus einer p_queue löscht, benötigt Zeit O(n). Alle anderen Methoden benötigen nur Zeit O(1).

Eine p_queue lohnt sich daher besonders dann, wenn hauptsächlich das Paar mit kleinster Priorität gefunden werden soll, und Prioritäten von bestimmten Paaren vermindert werden müssen.

Die Implementierung von p_queue ist effizienter als die von sortseq, bietet aber weniger Funktionalität. Es kann z. B. nicht nach einem Schlüssel (hier also nach einer Priorität) gesucht werden. Will man Schlüssel-Werte-Paare im Sinne eines assoziativen Containers speichern und gleichzeitig die Funktionalität einer Prioritäts-Warteschlange haben, so sollte man eine sortseq benutzen.

Weitere Informationen

Mehr über die Klasse p_queue findet sich auf der entsprechenden Manualseite. So liefert etwa der Subskript-Operator [] zu einem pq_item eine Referenz auf die Information des durch das Item referenzierten Paares; diese kann dadurch ausgelesen und abgeändert werden. Damit können z. B. Informationsänderungen in Reihe geschaltet werden:

PQ[it1] = PQ[it2] = new_i;

Übungen

Übung 41.

Erweitern Sie das Programm zur Huffman-Kodierung so, dass es den ursprünglichen Text in Huffman-Kodierung ausgibt und die Kompressionsrate berechnet.

Schreiben Sie das umgekehrte Programm, das (bei vorgegebener, hartverdrahteter Huffman-Kodierung) aus einer Huffman-kodierten Eingabe die ursprüngliche Abfolge der Zeichen berechnet.

Welche Datenstrukturen von LEDA benutzen Sie?

Übung 42.

Auch eine sortseq kann dazu verwendet werden, eine Priorität-Warteschlange zu implementieren. Formulieren Sie obige, verbesserte Version der Warteschlangen-Simulation mit Hilfe einer sortseq statt einer p_queue, und vergleichen Sie die Laufzeiten.

Übung 43.

Eine primitive Implementierung einer Prioritäts-Warteschlange besteht aus einer linearen Liste, in der die Container Paare (p,i) enthalten und nach aufsteigender Priorität geordnet sind. Kommt eine neues Paar (p,i) hinzu, wird vom Anfang der Liste an gesucht, bis die geeignete Stelle zum Einfügen gefunden wird. Wird eine Priorität p eines Paares (p,i) vermindert, muss das Paar eventuell nach links in der Liste wandern.

Implementieren Sie diese primitive Version einer Prioritäts-Warteschlange mit Hilfe einer list und vergleichen Sie die Laufzeiten im Warteschlangen-Simulationsprogramm.