Die Boost C++ Bibliotheken

Kapitel 17. Boost.Heap

Boost.Heap hätte auch Boost.PriorityQueue genannt werden können: Die Bibliothek stellt mehrere Priority-Queues zur Verfügung. Diese unterscheiden sich von std::priority_queue dahingehend, dass sie mehr Funktionen unterstützen.

Beispiel 17.1. boost::heap::priority_queue in Aktion
#include <boost/heap/priority_queue.hpp>
#include <iostream>

using namespace boost::heap;

int main()
{
  priority_queue<int> pq;
  pq.push(2);
  pq.push(3);
  pq.push(1);

  for (int i : pq)
    std::cout << i << '\n';

  priority_queue<int> pq2;
  pq2.push(4);
  std::cout << std::boolalpha << (pq > pq2) << '\n';
}

Beispiel 17.1 verwendet die Klasse boost::heap::priority_queue, die in der Headerdatei boost/heap/priority_queue.hpp definiert ist. Diese verhält sich grundsätzlich wie std::priority_queue, ermöglicht es aber, über die Elemente in der Queue zu iterieren. Die Reihenfolge der Elemente in der Iteration ist dabei zufällig.

Objekte vom Typ boost::heap::priority_queue können außerdem miteinander verglichen werden. Der Vergleich im Beispiel 17.1 gibt true zurück, weil pq mehr Elemente als pq2 hat. Hätten beide Queues gleich viele Elemente, würden diese paarweise miteinander verglichen werden.

Beispiel 17.2. boost::heap::binomial_heap in Aktion
#include <boost/heap/binomial_heap.hpp>
#include <iostream>

using namespace boost::heap;

int main()
{
  binomial_heap<int> bh;
  bh.push(2);
  bh.push(3);
  bh.push(1);

  binomial_heap<int> bh2;
  bh2.push(4);
  bh.merge(bh2);

  for (auto it = bh.ordered_begin(); it != bh.ordered_end(); ++it)
    std::cout << *it << '\n';
  std::cout << std::boolalpha << bh2.empty() << '\n';
}

Beispiel 17.2 stellt die Klasse boost::heap::binomial_heap vor. Diese Implementation einer Priority-Queue ermöglicht es nicht nur, geordnet über Elemente zu iterieren – also von Elementen mit der höchsten Priorität zu Elementen mit der niedrigsten. Priority-Queues vom Typ boost::heap::binomial_heap können verschmolzen werden. Dabei werden die Elemente der einen Queue zur anderen Queue hinzugefügt.

Im Beispiel wird für die Queue bh merge() aufgerufen und die Queue bh2 als Parameter übergeben. Der Aufruf von merge() führt dazu, dass die Zahl 4 von bh2 nach bh verschoben wird. bh enthält nach dem Aufruf vier Zahlen, während bh2 leer ist.

In der for-Schleife wird mit ordered_begin() und ordered_end() auf bh zugegriffen. ordered_begin() gibt einen Iterator zurück, mit dem über Elemente von höchster nach niedrigster Priorität iteriert werden kann. Beispiel 17.2 gibt demnach in der Schleife die Zahlen 4, 3, 2 und 1 in dieser Reihenfolge aus.

Beispiel 17.3. Elemente in einer boost::heap::binomial_heap ändern
#include <boost/heap/binomial_heap.hpp>
#include <iostream>

using namespace boost::heap;

int main()
{
  binomial_heap<int> bh;
  auto handle = bh.push(2);
  bh.push(3);
  bh.push(1);

  bh.update(handle, 4);

  std::cout << bh.top() << '\n';
}

boost::heap::binomial_heap ermöglicht es, Elemente zu ändern, nachdem sie der Queue hinzugefügt wurden. So wird im Beispiel 17.3 ein Handle gespeichert, der von push() zurückgegeben wird. Dieser Handle ermöglicht es, auf die in bh gespeicherte Zahl 2 zuzugreifen.

Mit update() bietet boost::heap::binomial_heap eine Methode an, der ein Handle übergeben werden kann, um das entsprechende Element zu ändern. Im Beispiel wird die Methode aufgerufen, um die Zahl 2 durch die Zahl 4 zu ersetzen. Wird anschließend mit top() das Element mit der höchsten Priorität abgefragt, wird 4 zurückgegeben.

boost::heap::binomial_heap bietet neben update() weitere Methoden an, um Elemente zu ändern. So können anstatt update() die Methoden increase() oder decrease() aufgerufen werden, wenn der Aufrufer weiß, dass die Änderung zu einer höheren oder niedrigeren Priorität führt. Im Beispiel 17.3 könnte update() durch increase() ersetzt werden, weil die Zahl von 2 auf 4 erhöht wird.

Neben boost::heap::priority_queue und boost::heap::binomial_heap stellt Boost.Heap weitere Implementationen zur Verfügung. Diese unterscheiden sich größtenteils in der Laufzeitkomplexität der verschiedenen Funktionen. So können Sie zum Beispiel eine Klasse boost::heap::fibonacci_heap verwenden, wenn Sie eine konstante Laufzeitkomplexität von push() wünschen. Die Dokumentation von Boost.Heap stellt die Laufzeitkomplexitäten der verschiedenen Klassen und Funktionen übersichtlich in einer Tabelle gegenüber.