Usa algoritmi heap STL in C++

1. Usa la funzione std::make_heap per convertire un intervallo in un heap
2. Usa la funzione std::sort_heap per ordinare un intervallo di heap
3. Usa la funzione std::pop_heap per rimuovere l’elemento successivo nell’heap

Questo articolo dimostrerà come utilizzare gli algoritmi di heap STL in C++.

Usa la funzione std::make_heap per convertire un intervallo in un heap

La funzione std::make_heap è fornita dagli algoritmi STL e può essere utilizzata per costruire una struttura di dati heap binaria dall’intervallo specificato. In genere, una struttura di dati heap è basata su albero e i due tipi comuni sono noti come heap max e heap min.

In un heap massimo, per qualsiasi nodo figlio, la chiave del nodo padre è maggiore o uguale alla chiave del figlio. D’altra parte, la chiave del genitore è inferiore alla chiave del bambino. Ora, la struttura heap costruita con la funzione make_heap è un heap binario simile a una struttura dati ad albero binario. Si noti che gli heap sono efficienti per le operazioni di inserimento e rimozione degli elementi, che possono essere eseguite in tempo logaritmico.

L’esempio seguente mostra la trasformazione del processo std::vector in un heap, quindi i contenuti vengono stampati utilizzando la consueta funzione printVector. Nota che l’ordine degli elementi è leggermente misterioso. In effetti, puoi leggerli come la struttura ad albero binario in cui il primo elemento è il valore della chiave radice.

Poiché ci sono solo due figli al massimo per ogni nodo in un albero binario, 82 e 39 seguono la radice come i figli. I prossimi due elementi sono i nodi figli di 82, e gli altri due sono posizionati sotto 39. Questa gerarchia soddisfa la proprietà max heap che l’elemento padre ha la chiave maggiore o uguale dei suoi figli.

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

Produzione:

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

Usa la funzione std::sort_heap per ordinare un intervallo di heap

Puoi utilizzare la funzione std::sort_heap per ordinare l’intervallo precedentemente convertito utilizzando la funzione std::make_heap. Il semplice sovraccarico della funzione std::sort_heap, che accetta solo due argomenti dell’iteratore, ordinerà il suono in ordine crescente. L’altro overload della funzione può accettare il terzo argomento della funzione di confronto con la seguente firma: bool cmp(const Type1 &a, const Type2 &b);. Dopo che l’intervallo è stato ordinato, non ha più la proprietà heap.

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

Produzione:

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

Usa la funzione std::pop_heap per rimuovere l’elemento successivo nell’heap

Le strutture heap di solito supportano operazioni di inserimento e rimozione rapida degli elementi. Le funzioni std::push_heap e std::pop_heap eseguono queste operazioni per l’intervallo heap in modo corrispondente. Quando il comando std::push_heap viene chiamato sull’intervallo heap, il suo primo elemento viene scambiato con l’ultima posizione e viene costruito un nuovo heap con gli elementi rimanenti. Si noti che l’heap è costruito come heap massimo per i parametri predefiniti. È possibile passare una funzione di confronto facoltativa come terzo argomento per modificare di conseguenza la gerarchia dell’heap.

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

Produzione:

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