Use STL Heap Algorithms em C++

1. Use a função std::make_heap para converter um intervalo em um heap
2. Use a função std::sort_heap para classificar um intervalo de heap
3. Use a função std::pop_heap para remover o próximo elemento no heap

Este artigo demonstrará como utilizar algoritmos de heap STL em C++.

Use a função std::make_heap para converter um intervalo em um heap

A função std::make_heap é fornecida nos algoritmos STL e pode ser usada para construir uma estrutura de dados de heap binário a partir de um determinado intervalo. Geralmente, uma estrutura de dados de heap é baseada em árvore e os dois tipos comuns são conhecidos como heap máximo e heap mínimo.

Em um heap máximo, para qualquer nó filho, a chave de seu nó pai é maior ou igual à chave do filho. Por outro lado, a chave do pai é menor que igual à chave do filho. Agora, a estrutura de heap construída com a função make_heap é um heap binário semelhante a uma estrutura de dados de árvore binária. Observe que os heaps são eficientes para as operações de inserção e remoção de elementos, que podem ser realizadas em tempo logarítmico.

O exemplo a seguir demonstra a transformação do processo std::vector em um heap e, em seguida, o conteúdo é impresso usando a função comum printVector. Observe que a ordem dos elementos é ligeiramente misteriosa. Na verdade, você pode lê-los como a estrutura de árvore binária em que o primeiro elemento é o valor da chave raiz.

Uma vez que existem apenas dois filhos no máximo para cada nó em uma árvore binária, o 82 e 39 seguem a raiz como os filhos. Os próximos dois elementos são os nós filhos de 82 e os outros dois estão posicionados em 39. Essa hierarquia satisfaz a propriedade de heap máximo de que o elemento pai tem a chave maior ou igual a seus filhos.

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

Resultado:

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

Use a função std::sort_heap para classificar um intervalo de heap

Você pode utilizar a função std::sort_heap para classificar o intervalo convertido anteriormente usando a função std::make_heap. A sobrecarga simples da função std::sort_heap, que leva apenas dois argumentos de iterador, classificará o intervalo em ordem crescente. A outra sobrecarga da função pode aceitar o terceiro argumento da função de comparação com a seguinte assinatura: bool cmp(const Type1 &a, const Type2 &b);. Depois que o intervalo é classificado, ele não tem mais a propriedade 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;
}

Resultado:

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

Use a função std::pop_heap para remover o próximo elemento no heap

As estruturas de heap geralmente oferecem suporte a operações rápidas de inserção e remoção de elementos. As funções std::push_heap e std::pop_heap conduzem essas operações para o intervalo de heap de maneira correspondente. Quando o comando std::push_heap é chamado no intervalo de heap, seu primeiro elemento é trocado com a última posição e um novo heap é construído com os elementos restantes. Observe que o heap é construído como um heap máximo por parâmetros padrão. Pode-se passar uma função de comparação opcional como o terceiro argumento para modificar a hierarquia do heap de acordo.

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

Resultado:

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