Verwenden von STL-Heap-Algorithmen in C++

1. Verwenden Sie die Funktion std::make_heap, um einen Bereich in einen Heap umzuwandeln
2. Verwenden Sie die Funktion std::sort_heap, um einen Heap-Bereich zu sortieren
3. Verwenden Sie die Funktion std::pop_heap, um das nächste Element im Heap zu entfernen Remove

In diesem Artikel wird gezeigt, wie Sie STL-Heap-Algorithmen in C++ verwenden.

Verwenden Sie die Funktion std::make_heap, um einen Bereich in einen Heap umzuwandeln

Die Funktion std::make_heap wird unter den STL-Algorithmen bereitgestellt und kann verwendet werden, um eine binäre Heap-Datenstruktur aus dem angegebenen Bereich zu erstellen. Im Allgemeinen ist eine Heap-Datenstruktur baumbasiert, und die beiden gängigen Typen sind als Max-Heap und Min-Heap bekannt.

In einem Max-Heap ist für jeden untergeordneten Knoten der Schlüssel seines übergeordneten Knotens größer oder gleich dem Schlüssel des untergeordneten Knotens. Andererseits ist der Schlüssel des Elternteils kleiner als der Schlüssel des Kindes. Nun ist die mit der Funktion make_heap erstellte Heap-Struktur ein binärer Heap, ähnlich einer binären Baumdatenstruktur. Beachten Sie, dass Heaps effizient für das Einfügen und Entfernen von Elementen sind, die in logarithmischer Zeit ausgeführt werden können.

Das folgende Beispiel demonstriert die Transformation des std::vector-Prozesses in einen Heap, und dann wird der Inhalt mit der üblichen printVector-Funktion gedruckt. Beachten Sie, dass die Reihenfolge der Elemente etwas mysteriös ist. Tatsächlich können Sie sie als binäre Baumstruktur lesen, wobei das erste Element der Wurzelschlüsselwert ist.

Da es für jeden Knoten in einem Binärbaum maximal zwei Kinder gibt, folgen die 82 und 39 als Kinder auf die Wurzel. Die nächsten beiden Elemente sind die Kinderknoten von 82 und die anderen beiden sind unter 39 positioniert. Diese Hierarchie erfüllt die max heap-Eigenschaft, dass das übergeordnete Element den Schlüssel größer oder gleich als seine untergeordneten Elemente hat.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
  cout << "vec1 original:  ";
  printVector(vec1);

  std::make_heap(vec1.begin(), vec1.end());
  cout << "vec1 make_heap: ";
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

vec1 original:  11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;

Verwenden Sie die Funktion std::sort_heap, um einen Heap-Bereich zu sortieren

Mit der Funktion std::sort_heap können Sie den zuvor konvertierten Bereich mit der Funktion std::make_heap sortieren. Die einfache Überladung der Funktion std::sort_heap, die nur zwei Iteratorargumente benötigt, sortiert den Rang in aufsteigender Reihenfolge. Die andere Überladung der Funktion kann das dritte Argument der Vergleichsfunktion mit der folgenden Signatur akzeptieren: bool cmp(const Type1 &a, const Type2 &b);. Nachdem der Bereich sortiert wurde, verfügt er nicht mehr über die Heap-Eigenschaft.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::sort_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;

Verwenden Sie die Funktion std::pop_heap, um das nächste Element im Heap zu entfernen Remove

Haufenstrukturen unterstützen normalerweise schnelle Elementeinfügungs- und -entfernungsvorgänge. Die Funktionen std::push_heap und std::pop_heap führen diese Operationen für den Heap-Bereich entsprechend durch. Wenn der Befehl std::push_heap für den Heap-Bereich aufgerufen wird, wird sein erstes Element mit der letzten Position vertauscht und mit den restlichen Elementen ein neuer Heap konstruiert. Beachten Sie, dass der Heap standardmäßig als Max-Heap erstellt wird. Als drittes Argument kann eine optionale Vergleichsfunktion übergeben werden, um die Heap-Hierarchie entsprechend zu ändern.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::pop_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Ausgabe:

91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;