Dieser Text von 1988 beschreibt ausführlich eine wichtige Datenstruktur. Die Struktur wird hier - wie bei einem ADT - zusammen mit den Operationen auf dieser Struktur behandelt. Ganz allgemein und im strengen Sinne wird sie hier nicht als ADT abgehandelt, denn es stehen unterrichtliche Anwendungen im Hintergrund, die mit den relativ einfachen Möglichkeiten von Pascal realisiert werden sollen, im besonderen also auch ohne Objekte.

Der Text war lange Zeit mit nur geringen Modifikationen eine Grundlage für den Informatikunterricht in Jahrgangsstufe 13. Die beigefügten Programmbeispiele sind ehemals für TurboPascal 3 entwickelt worden und jetzt auch noch unter TurboPascal 7 lauffähig. Der Text in der alten Form für DOS ist jetzt in eine zeitgemäßere Form übertragen worden. Dabei ist der Text ergänzt und verbessert worden. Außerdem wurden weitere Beispiele beigefügt.

Die Bezeichnung Heap wird in zwei verschiedenen Zusammenhängen benutzt:

• für den vom Laufzeitsystem verwalteten freien Speicher, wo z.B. dynamische Datenstrukturen angelegt werden,
• für einen ADT mit bestimmten Eigenschaften.

Andere Bezeichnungen für den ADT Heap sind:

• priority queue (besonders bei bestimmten Anwendungen)
• Haufen (als wörtliche Übersetzung)
• Halde (eigentlich eine falsche Übersetzung)
• Stadel (so wird dieser ADT zum Beispiel bei der Fernuni bezeichnet).

Diese Bezeichnungen treffen entweder nicht (Haufen,Halde) oder sind ungebräuchlich (Stadel) oder aber zu kompliziert (priority queue). Deshalb bleiben wir bei der allgemein verbreiteten Bezeichnung Heap.

Der Heap ist einerseits ein ADT und könnte dabei als nichttriviales Beispiel dienen. Der Heap kann andererseits als Binärbaum aufgefaßt werden und dabei als Beispiel dafür dienen, daß Bäume effektiv im Array realisiert werden können. Zwei prominente Anwendungen des ADT Heap sind der "Heapsort" und der Algorithmus "Branch & Bound".

Eine informelle Definition eines Heaps:  Es sei n   aus   N eine Konstante. Es sei T ein Typ, auf dem eine Bewertung definiert ist. Ein Heap of T ist eine Datenstruktur, in der 0 bis n Objekte vom Typ T so gespeichert werden können, daß auf das Element mit der besten Bewertung direkt zugegriffen werden kann. Gebräuchliche Operationen auf einem Heap sind:

• einen leeren Heap erzeugen,
• die Anzahl der Elemente eines Heaps abfragen,
• ein Element in den Heap einbringen,
• das beste Element des Heaps erfragen,
• das beste Element des Heaps entfernen,
• aus einem Array einen Heap machen,
• alle Elemente ab einer bestimmten Bewertung entfernen.

Aus logischer Sicht kann man einen Heap als speziellen Binärbaum auffassen. Dabei braucht man nicht berücksichtigen, daß in der Praxis die Anzahl der Elemente eines Heaps eine feste Obergrenze hat. Man braucht auch keine spezielle Implementierung des Heap im Kopf haben.

Ein Heap ist ein Binärbaum mit folgenden Eigenschaften:

• Unterbäume eines Heaps sind Unterheaps.
• Die Wurzel eines Heaps hat eine Bewertung, die besser ist, als die Bewertung der Wurzeln der beiden Unterheaps, sofern diese nicht leer sind.
• Ein Heap ist vollständig, bis auf die letzte Schicht.
• Wenn die letzte Schicht nicht vollständig ist, dann müssen die vorhandenen Elemente von links beginnend ohne Lücken in der Schicht liegen.

Die Wurzel des Heaps ist das Element mit der besten Bewertung. Diese kann man direkt ansehen und diese ist das einzige Element des Heaps, das man direkt ansehen kann. Diese Operation kostet offenbar O(1).

Das Entfernen des besten Elements läuft folgendermaßen ab: der äußerst rechte Knoten der letzten Schicht wird gelöscht, sein Inhalt in die Wurzel gesetzt. Jetzt wird der Unterheap gesucht, der besser bewertet ist. Die Wurzel dieses Unterheaps wird mit dem Vaterknoten ausgetauscht. Dann wird der betreffende Unterheap betrachtet, seine Wurzel mit den Söhnen verglichen, ggf. ausgetauscht usw. Das Verfahren endet, wenn kein Austausch nötig oder nicht mehr möglich ist. Diese Operation kann iterativ oder rekursiv geschrieben werden. Der Kern dieser Operation ist bekannt als der Algorithmus "sift" (von Robert Floydd) oder "senke". Diese Operation ist abhängig von der Baumtiefe und kostet deshalb O(log n).

Ein beliebiges Element kann in den Heap folgendermaßen eingefügt werden: Das Element wird als äußerst rechter Knoten der untersten Schicht eingefügt. Nun wird es mit seinem Vaterknoten verglichen. Sohn und Vater werden vertauscht, falls der Sohn besser bewertet ist. Das geht solange bis die Wurzel des Heap erreicht ist oder kein Austausch nötig ist. Diese Operation kostet auch O(log n).

Die Operationen, die mit mehreren Elementen befaßt sind (aus einem Array einen Heap machen; alle Elemente entfernen, die schlechter als ein bestimmter Wert sind), kann man sinnvoll erst dann diskutieren, wenn man eine bestimmte Implementierung im Sinn hat. Es sei ohne weitere Erläuterung angemerkt, daß diese Operationen einen Aufwand von O(n) haben.

Ein vollständiger Binärbaum (in dem Sinne, daß nur rechte Knoten in der untersten Schicht fehlen können) mit n Knoten kann strukturell äquivalent in einem ARRAY [1..m] OF Knoten mit  m >= n  dargestellt werden.

• Die Wurzel steht im Array an Position 1.
• Wenn ein Knoten an Position i steht, dann ist der Knoten die Wurzel, wenn i=1.
• Wenn ein Knoten an Position i steht und wenn v := i DIV 2 und v >= 1 ist, dann ist v der Index des Vaters des Knotens.
• Wenn ein Knoten an Position i steht und wenn l := i * 2 und l <= n ist, dann ist l der Index des linken Sohnes des Knotens.
• Wenn ein Knoten an Position i steht und wenn r := i * 2 + 1 und r <= n ist, dann ist r der Index des rechten Sohnes des Knotens.
• Wenn ein Knoten an Position i steht und wenn 2 * i > n ist, dann ist der Knoten ein Blatt.

In der folgenden Graphik wird verdeutlich, weshalb man hier von schichtweiser Darstellung redet, denn die Schichten liegen hintereinander im Array. Dies ist die gebräuchliche Art, in der man einen Heap realisiert.

Aufgabe g)   (zur Lösung) Ein Binärbaum mit 50 Knoten ist in einem passendem Array gespeichert. Wenn i der Index eines Knotens im Array ist, geben Sie den Index von Vater und Söhnen an, falls diese existieren. i = 1, 12, 13, 24, 25, 30

Aufgabe h)   (zur Lösung) i)    Ist es möglich n-Bäume im Array darzustellen ? ii)   Können auch nicht vollständige Bäume im Array dargestellt werden ?

Aufgabe i)   (zur Lösung) Wägen Sie Vor- und Nachteile der Realisierung von Bäumen im Array gegenüber einer Realisierung mit Zeigern ab.

4. Eine Implementation

Eine vereinfachte Implementation liegt in der Datei  HPLIGHT.PAS   vor. Diese Version ist allerdings speziell für die Anwendung in   DYNPROG   und   DYNBABA   geschaffen und nicht so vielseitig, wie es möglich wäre. Eine allgemeinere Version wird hier als   HPADT.PAS   gegeben und das ist die Version, auf die sich dieser Text vornehmlich bezieht.

Bekanntlich lassen sich in normalem Pascal keine ADTs im Sinne der reinen Lehre formulieren. Dafür fehlen generische Typen und vor allem generische Operationen. Anwendungsspezifisch müssen immer noch Typen festgelegt werden und außerdem bleiben alle einschränkenden Regeln für Deklarationen natürlich in Kraft. Eine objektorientierte Lösung wird hier nicht diskutiert.

Vom ADT Heap, der in einem Array realisiert werden soll, braucht der Anwender nur die funktionale Beschreibung der Operationen kennen und die Typen, die vom ADT bereitgestellt werden. Zusätzlich muß er das Interface kennen, das heißt die problemspezifischen Teile, die der ADT braucht und die der Anwender zuvor im Hauptprogramm deklariert haben muß.

Beide Informationen werden hier in Pascal-Notation gegeben, um eine spätere Realisierung zu vereinfachen und um den ADT für den Gebrauch zu präzisieren.

4.1 Anwender-Interface

Hier wird noch die alte Technik der Include-Dateien verwendet, die hier immer noch ausreichend ist, um die intendierten Inhalte transparent zu machen und um schnell zu lauffähigen Programmbeispielen zu kommen. Im Hauptprogramm, das die hier beschriebene Datenstruktur benutzen soll, muß bei den Deklarationen vor Einbindung der Include-Datei, folgende deklariert sein:

  CONST  n_heap         = ...;   {Integer, max. Heapgröße}
  TYPE   inhalt_heap    = ...;   {Inhalt der Heapknoten incl. Bewertung}

  FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
  {Auf den Inhalten des Heaps wird eine Vergleichsoperation  realisiert.
  Wirkung: (bewertung(b)  <=  bewertung(a)).  Anwenderspezifisch !}

  FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
  {Auf den Inhalten des Heaps wird eine Vergleichsoperation  realisiert.
  Wirkung: (bewertung(b)  >=  bewertung(a)).  Anwenderspezifisch !}

  {$I HPADT.PAS}

4.2 funktionale Beschreibung

Dem Anwender werden vom Paket   HPADT.PAS   zwei Typen zur Verfügung gestellt. Einmal ein Aufzählungstyp zur Charakterisierung des Heaps und dann der Heap selbst mit den drei Komponenten "last" für den Index des letzten Elements im Feld. Dann das "feld", das hier als Array auch für andere Zugriffe dann noch offen ist, was zwar gegen die Philosophie der ADTs verstößt, aber die ganz reine Lehre kann man an der Universität immer noch genießen. Schließlich wird in "art" noch der Heap charakterisiert.

  TYPE  heap_art   = (undef_heap, min_heap, max_heap);
        heap_typ   = RECORD
                       last: Integer;
                       feld: ARRAY [1..n] OF inhalt_heap;
                       art : heap_art
                     END;

Das Paket stellt dann neun Funktionen/Prozeduren zur Verfügung, mit denen die üblichen Operationen für Heaps durchgeführt werden können. Nicht vorhanden sind Ein-/Ausgabeprozeduren. Sollten die dennoch einmal nötig sein, so können sie leicht realisiert werden, weil die Array-Struktur des Heaps ja bekannt ist.

  {1}
  PROCEDURE  create_heap (VAR h: heap_typ; art: heap_art);
  {Erzeugt einen leeren Heap "h", je nach "art" als Minimum- oder Maximum-Heap.}

  {2}
  PROCEDURE  make_heap (VAR h: heap_typ; anz: Integer; art: heap_art);
  {Im Objekt "h" ist die Komponente "h.feld" mit "anz" Elementen
   bereits gefüllt, allerdings noch ohne Heapstruktur. Anders
   ausgedrückt: es liegt ein Array mit belegten Elementen
   vor und dies Array wird zu einem Heap transformiert; je
   nach "art" zu Minimum- oder Maximum-Heap.}

  {3}
  FUNCTION   count_heap (VAR h: heap_typ): Integer;
  {Der Funktionswert ist die Anzahl der Elemente im Heap "h", 0 <= anzahl <= n.}

  {4}
  FUNCTION   empty_heap (VAR h: heap_typ): Boolean;
  {Ist True, wenn der Heap leer ist.}

  {5}
  FUNCTION   full_heap (VAR h: heap_typ): Boolean;
  {Ist True, wenn der Heap voll ist.}

  {6}
  PROCEDURE  in_heap (VAR h: heap_typ; VAR inh: inhalt_heap);
  {Das Element "inh" wird, falls möglich, in den Heap "h" eingefügt. Auf den
   freien Platz hinter dem letzten Element des Heaps wird der Inhalt "inh"
   gesetzt. Dann wird das Element solange hochgeschaukelt, bis es eine Position
   gefunden hat, die seiner Bewertung entspricht.}

  {7}
  PROCEDURE  best_heap (VAR h: heap_typ; VAR inh: inhalt_heap);
  {Das oberste Element des Heaps "h", im Minimum-Heap das minimale und im
   Maximum-Heap das maximale Element, wird im Parameter "inh" abgeliefert.
   Der Heap bleibt unverändert.}

  {8}
  PROCEDURE  delbest_heap (VAR h: heap_typ);
  {Das beste Element des Heaps "h", also entweder Minimum oder Maximum, je
   nach Art des Heaps, wird unter Erhaltung der Heapstruktur entfernt.}

  {9}
  PROCEDURE  clean_heap (VAR h: heap_typ; VAR b: inhalt_heap);
  {Im Heap "h" werden alle Elemente mit einer Bewertung die schlechter
   oder gleich  "b" ist unter Erhaltung der Heapstruktur entfernt. }

4.3 Anmerkungen zur Implementation

Die Bewertung des Heaps wird irgendwie auf die <= oder >= Relation zurückgeführt. Das ist immer anwenderspezifisch und könnte bei komplizierten Inhaltstypen nicht trivial sein. Das geschieht notwendigerweise im Hauptprogramm im Anwenderinterface in den FUNCTIONs "kleinergleich" bzw. "groessergleich".

Ein Heap mit der <= Relation heißt Minimum-Heap, einer mit >= Relation dann Maximum-Heap. Der ADT stellt diese beiden Attribute zur Verfügung, die beim Erzeugen eines Heaps festgelegt werden müssen.

Die Array-Struktur des Heaps liegt offen. Zu jedem Zeitpunkt liefert die Funktion "count" die Anzahl der gültigen Arrayeinträge, d.h. die Anzahl der Elemente des Heaps. Damit sind Operationen nur auf der Array-Struktur wie Ausgabe aller Elemente des Heaps oder Inkrementieren aller Elemente des Heaps einfach zu realisieren.

Die Operationen "create_heap", "count_heap", "empty_heap", "full_heap" und "best" sind ganz einfach und brauchen nicht weiter erläutert werden.

Die Operationen "delbest_heap" unter Verwendung von "sift" und "in_heap" sind bereits in Abschnitt 2 und in den Aufgaben a),b) und f) angemerkt worden.

Es bleiben die Operationen "make_heap" und "clean_heap" zu betrachten. Diese sind nicht trivial. Sie operieren auf dem gesamten Heap und kosten höchstens O(n*log(n)).

"mache_heap" : Blätter braucht man erst mal nicht betrachten, deshalb beginnt man im Array bei der Position n DIV 2, wenn n Elemente im Heap sind. In einer Schleife von n DIV 2 bis 1 betrachte man alle Knoten und senke diese Knoten an die richtige Position. Dafür muß die Prozedur "sift" so formuliert sein, daß sie mit einem beliebigen Knoten arbeiten kann.

Für die Operation "clean_heap" muß man das ganze Array von 1 bis count_heap(h) durchmustern, die Bewertung jedes einzelnen Knotens mit dem Vergleichswert überprüfen und falls der Knoten schlechter ist, dann muß ablaufen:

• vertausche den Inhalt des allerletzten Knotens mit dem aktuellen,
• die Zahl der Elemente des Heaps wird um 1 vermindert.

Zum Schluß ist das Array allerdings kein Heap mehr. Deshalb muß danach "make_heap" ablaufen.

Verwenden Sie den ADT Heap für ein Programm, das die Heapoperationen "create_heap", "in_heap", "delbest_heap" und "clean_heap" veranschaulicht. Das Programm soll nach Wahl einen Minimum- oder Maximum-Heap bearbeiten können. Nutzen Sie die Array-Struktur aus, um zusätzlich eine "ausgabe" zu schaffen, die den ganzen Heap zeigt.

   CONST  n_heap         = 25;    {Integer, max. Heapgröße}
   TYPE   inhalt_heap    = Char;  {Inhalt der Heapknoten incl. Bewertung}
      
   FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
   BEGIN     kleinergleich:=(b<=a)  END;

   FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
   BEGIN     groessergleich:=(b>=a)  END;

Mit diesen Deklarationen kann der Heap benutzt werden. Das Programm selbst ist schlicht und auch die Ausgabe ist keine Herausforderung. Man lese den Quelltext   HEAP1.PAS   und versuche vielleicht dann noch die eine oder andere Verbesserung anzubringen.

Verwenden Sie den ADT Heap für ein Programm, das ein Array sortieren kann. Benutzen Sie als Array direkt das Array im Heap. Verfassen Sie eine entsprechende Eingabe- und Ausgabeprozedur. Der Sortieralgorithmus soll folgendermaßen ablaufen:

• mache aus dem Array einen Maximum-Heap
• laufe vom letzten Platz im Array bis zum 2.Platz und nehme das aktuelle Maximum vom Heap, entferne das Maximum vom Heap und schreibe das Maximum an die gerade aktuelle Position.

Begründen Sie, warum dieser Algorithmus funktioniert. Vergleichen Sie die Anzahl der Vergleichsoperationen beim "Heapsort" mit den bekannten Sortierverfahren. Zusatz für Experten: bestimmen Sie die Anzahl der Vergleiche in der O-Notation.

Die Deklarationen zum Anwender-Interface im Hauptprogramm sind naheliegend und ohne Überraschungen:

   CONST n_heap        = ..;       {Integer, max. Heapgröße}
   TYPE  inhalt_heap   = Integer;  {Inhalt der Heapknoten incl.Bewertung}
      
   FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
   BEGIN     kleinergleich:=(b<=a)  END;

   FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
   BEGIN     groessergleich:=(b>=a)  END;

Das Programm ist nach obigen Anmerkungen schnell gemacht. Allein mit den Operationen des ADT kommt man allerdings nicht aus. Man muß auch noch direkt in das Array eingreifen.

   Es kostet:     "mache_heap"             O(n)
                  "best_heap"              O(1)
                  "delbest_heap"           O(log(n))

   zusammen:

   BEGIN
     mache_heap (h,n,max_heap);            O(n) +
     FOR index := n  DOWNTO 2 DO           n * (
       best_heap (h,bestes);                    O(1) +
       delbest_heap (h);                        O(log(n))
       h.feld[index] := bestes
     END                                        )
   END;
                                           O(n) + n*(O(1)+O(log(n))
                                         = O(n) + O(n*log(n))
                      Heapsort           = O(n*log(n))

   zum Vergleich:     Bubblesort           O(n²)
                      Quicksort            O(n*log(n))

Das Programm nach diesem Entwurf steht als   HEAP2.PAS   im Quelltext zur Verfügung.

In der Literatur wird der Heapsort sehr viel kürzer und knapper formuliert, indem die Heapoperationen nicht mehr explizit ausgeführt werden, sondern nur im notwendigen Umfang direkt in den Algorithmus eingebaut werden. Das hat zur Folge, daß der Heapsort ohne weitere Erläuterungen oder Vorkenntnisse aus dem Programmtext her kaum verständlich ist.

Dieses Programm zeigt dagegen exakt warum der Heapsort so heißt und mit Kenntnis des Heaps ist es sicher leicht durchschaubar.

Verwenden Sie den ADT Heap für ein Programm, das den Heap als "priority queue" benutzt. Es soll stark vereinfacht die Zuteilung von Bausparverträgen simuliert werden. Zuerst werden Namen und Bewertungszahlen (10..1000) eingegeben und in einen Heap eingefügt. Dann läuft das Programm in einer Schleife, wobei in einer Phase immer folgendes abläuft:

• es können weitere Namen und Bewertungszahlen eingegeben werden,
• die Zuteilung wird veranlaßt, das heißt die ersten drei Namen mit den besten Bewertungszahlen werden ausgegeben,
• alle noch vorhanden Einträge werden in der Bewertung um 100 Punkte erhöht.

Benutzen Sie die Arraystruktur, um alle Einträge in der Bewertung zu erhöhen. Ändert sich durch eine solche Aktion die Heapstruktur ?

   CONST     n_heap         = 1000;    {max. Heapgröße}
   TYPE      inhalt_heap    = RECORD   {Inhalt der Heapknoten incl. Bewertung}
                                wert: Integer;
                                name: String[10]
                              END;

   FUNCTION  kleinergleich (b,a: inhalt_heap): Boolean;
   BEGIN     kleinergleich:=(b.wert<=a.wert)  END;

   FUNCTION  groessergleich (b,a: inhalt_heap): Boolean;
   BEGIN     groessergleich:=(b.wert>=a.wert)  END;

Das Programm nach diesem Entwurf steht als HEAP3.PAS im Quelltext und als EXE-Datei in einer ganz einfachen Version zur Verfügung. Es ist klar, daß dieses Programm keine vernünftige Simulation darstellt, es ist sozusagen eine minimale Anwendung des Heaps als Schlange mit Prioritäten.

In diesem Programm wird in den Heap intern eingegriffen, also nicht über die zur Verfügung gestellten Prozeduren. Die Prozedur "erhoehe" operiert direkt auf den Heapelementen. Das ist an sich ein Verstoß gegen die Prinzipien eines ADT, aber was wäre denn die Alternative ? Die Prozedur "erhoehe" verändert den Heap nicht in seiner Struktur, denn alle Elemente werden um den gleichen Wert erhöht und dabei bleibt was vorher kleiner war auch hinterher noch kleiner.

Ein einfaches Überdeckungsproblem: Gegeben sind N Münzen mit den Münzwerten w1, w2, .. , wN und ein Betrag B. Gesucht ist eine Möglichkeit, den Betrag B mit möglichst wenig Münzen auszuzahlen.

Dies Problem ist klassisch und kann auch sehr gut mit Backtracking behandelt werden. Meist ist aber Branch & Bound das effektivste Verfahren. Das liegt daran, daß nach der ersten gefundenen Lösung der Heap, der die noch lebenden Knoten enthält, aufgeräumt wird und dabei der noch abzusuchende Lösungsraum oft drastisch eingegrenzt werden kann.

An dieser Stelle wird nicht auf das Verfahren Branch & Bound selbst eingegegangen. Das erfolgt an anderer Stelle. Hier steht lediglich der die Anwendung des Heap im Blickpunkt.

   CONST    n_heap      = 500;          {max. Heapgröße}
   TYPE     inhalt_heap = RECORD        {Inhalt der Heapknoten incl. Bewertung}
                            wert: Integer;
                            tup : tupel
                          END;

   FUNCTION kleinergleich (b,a: inhalt_heap): Boolean;
   BEGIN    kleinergleich:=(b.wert<=a.wert)  END;

   FUNCTION groessergleich (b,a: inhalt_heap): Boolean;
   BEGIN    groessergleich:=(b.wert>=a.wert)  END;

Hier ist der Inhaltstyp des Heaps ein Record mit einer Komponente "wert", die den Boundfunktionswert enthält und nach dessen Wert der Minimum-Heap aufgebaut wird. Die wesentliche Information ist dann die Komponente "tup", in der die Lösungsvektoren gespeichert werden.

Die Anwendung des ADT Heap ist hier ohne Haken und Ösen. Die wichtige Operation "clean_heap" ist bereits implementiert.

Für dieses Beispiel soll hier noch die Zielfunktion und eine Boundfunktion angegeben werden, damit das konkrete Beispielprogramm   HEAP4.PAS   nachvollziehbar wird.

Diese Boundfunktion ist gültig, wie man leicht nachprüfen kann.

1. falls k=n, dann ist fb(V) = f(V)

2. falls k<n, dann ist fb(V^k) <= fb(V^k+1) wobei V^k+1 für alle Fortsetzungen von V^k steht.

Für ein kleines Zahlenbeispiel kann man den Lösungsraum noch vollständig als Baum von Bitvektoren aufzeichnen. Mit 5 Münzen hätte der vollständige Baum 2⁶-1 = 63 Vektoren insgesamt, davon 2⁵ = 32 Blätter als Endpunkte. Wie wirksam Äste des Baumes als "tot" erkannt und abgeschnitten werden, hängt auch von den Daten ab und ist damit oft unvorhersehbar. Bei diesem Beispiel werden nur noch 21 Vektoren erzeugt, davon nur 2 Blätter. Demgegenüber bringt es ein Ansatz mit Backtracking beim gleichen Zahlenmaterial auf 39 Vektoren, davon 16 Blätter.

Die roten Nummern oben links an den Bitvektoren sollen in der folgenden Graphik die Reihenfolge anzeigen, in der die Bitvektoren erzeugt werden. Die exakte Reihenfolge ist stark abhängig vo der Implementation des Heaps, besonders davon wie Vektoren mit gleichem Wert eingeordnet werden.

Man mag einwenden, daß dies Beispiel so konstruiert ist, daß B & B besonders gut abschneidet und daß man andere Verfahren auch noch steigern könnte. Da ist etwas dran, aber dennoch hat B & B den Vorteil, daß die noch lebenden Vektoren im Heap mit schlechterem Boundfunktionswert immer dann gar nicht mehr untersucht werden, sobald schon eine Lösung gefunden ist. Wenn B & B eine Lösung schnell finden kann, wenn man eventuell schon mit einer Näherungslösung starten kann, dann wirkt sich dieser Vorteil massiv aus.