priority - min heap c++

¿Cuándo debo usar make_heap vs. Priority Queue?

Question

Tengo un vector que quiero usar para crear un montón. ¿No estoy seguro de si debo usar la función make_heap de C ++ o poner mi vector en una cola de prioridad? ¿Cuál es mejor en términos de rendimiento? ¿Cuándo debo usar uno frente al otro?

Answer 1

Si no desea modificar ese vector, entonces debe usar la priority queue ya que crea un vector separado. Pero, si puede permitirse editarlo, obviamente utilizar make_heap sería mejor, ya que no crea un espacio auxiliar y modifica ese vector en el lugar y, por lo tanto, ahorra espacio. Además, la cola de prioridad es fácil de implementar. Por ejemplo, cuando usa make_heap mientras hace estallar un elemento, tiene que usar dos comandos, primero pop_heap y luego pop_back .. pero puede hacerlo con un solo comando en caso de que haya una cola de prioridad. Del mismo modo, mientras se empuja el elemento en el montón.

Ahora, el rendimiento de ambos sería el mismo porque la cola de prioridad no es un contenedor y utiliza algún contenedor subyacente como vector o deque que usa las mismas operaciones de almacenamiento dinámico utilizadas por las operaciones make_heap. Por lo tanto, debe usar uno dependiendo de sus requisitos.

Answer 2

Una prioridad_cinta se implementa (al menos normalmente) como un montón. Como tal, la verdadera pregunta es si la prioridad_queue proporciona lo que necesita. Cuando usas make_heap todavía tienes acceso a todos los elementos. Cuando utiliza la prioridad_cinta, solo tiene unas pocas operaciones que dan acceso muy limitado a los elementos (básicamente, solo inserte un elemento y elimínelo al principio de la cola).

Answer 3

make_heap permite la flexibilidad al costo de la encapsulación, como ejemplo, la impresión del montón.

Un uso interesante de make_heap es una ordenación de combinación en el lugar que utiliza make_heap en un lado de la combinación, para lograr la fusión en el peor de los casos en lugar de n / 2 (log (n / 2)).

Este ejemplo muestra el uso del vector de entrada y la impresión del montón creado:

#include <queue>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void print(string prefix,vector<int>& v)
{
  cout << prefix;
  for(int i : v)
     cout << i << " ";
  cout << endl;
}

int main()
{
  vector<int> v={1,2,9,0,3,8,4,7,1,2,9,0,3,8,4,7};
  typedef priority_queue< int,vector<int>,greater<int> > MinQ;
  MinQ minQ(v.begin(),v.end()); //minQ
  print("After priority_queue constructor: ",v);

  make_heap(v.begin(),v.end(),greater<int>());
  print("After make_heap: ", v);
  return 0;
}

Salida:

After priority_queue constructor: 1 2 9 0 3 8 4 7 1 2 9 0 3 8 4 7
After make_heap: 0 1 0 1 2 3 4 7 2 3 9 8 9 8 4 7

Answer 4

priority_queue no es un contenedor. Es un adaptador de contenedor que utiliza un contenedor subyacente específico, por ejemplo, vector o deque , y proporciona un conjunto específico de métodos para trabajar con los datos. Además, su implementación se basa en los algoritmos *_heap .

Por ejemplo, cada vez que presiona un nuevo valor al vector , debe llamar a push_heap para extender un rango considerado como un montón. Si no usa la priority_queue , le permite considerar, por ejemplo, la mitad del vector como montón ( std::make_heap(v.begin(), v.begin() + (v.size() / 2)) ), mientras que otra mitad será como está.

Lo que la priority_queue hace cuando llama a push en él: empuja un nuevo elemento a la parte posterior del contenedor subyacente y llama a push_heap para mantener la propiedad del montón priorizada (solo importa que el primer elemento sea el más grande).

Diría que es mejor que considere el diseño de la solución y sus requisitos específicos, en lugar de los problemas de rendimiento.

Answer 5

Estándar C ++ 11

El borrador estándar de C ++ 11 N3337 especifica que se utiliza std::make_heap en el constructor de std::priority_queue en "23.6.4.1 constructores de priority_queue":

Priority_queue explícito

2 Efectos: Inicializa comp con x y c con y (copie la construcción o mueva la construcción según corresponda); llama a make_heap (c.begin (), c.end (), comp).

Y otros métodos dicen:

void push (const value_type & x);

Efectos: c.push_back (x); push_heap (c.begin (), c.end (), comp)

Sin embargo, a partir del n4724 más reciente, la redacción de los métodos que no son de constructor se convierte en "como si", por lo que creo que no se garantiza una llamada real a los métodos de *_heap , solo su comportamiento funcional.

Paso de depuración en la fuente g++ 6.4 stdlibc ++ para confirmar que la priority_queue make_heap a make_heap

En el paquete g++-6 predeterminado de Ubuntu 16.04 o en una compilación GCC 6.4 desde la fuente , puede ingresar a la biblioteca de C ++ sin ninguna configuración adicional.

Usando eso, podemos confirmar fácilmente que std::priority_queue es solo un envoltorio sobre la familia std::make_heap con un std::vector subyacente, lo que implica que el rendimiento será el mismo.

a.cpp:

#include <cassert>
#include <queue>

int main() {
    std::priority_queue<int> q;
    q.emplace(2);
    q.emplace(1);
    q.emplace(3);
    assert(q.top() == 3);
    q.pop();
    assert(q.top() == 2);
    q.pop();
    assert(q.top() == 1);
    q.pop();
}

Compilar y depurar:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex ''start'' -q --args a.out

Ahora, si entras en el constructor std::priority_queue<int> q primero ingresa en un vector constructor, por lo que ya podemos adivinar que std::priority_queue contiene un std::vector .

Ahora ejecutamos finish en GDB para encontrar el constructor de colas y entramos nuevamente, lo que nos lleva al constructor de colas real /usr/include/c++/6/bits/stl_queue.h :

443       explicit
444       priority_queue(const _Compare& __x = _Compare(),
445              _Sequence&& __s = _Sequence())
446       : c(std::move(__s)), comp(__x)
447       { std::make_heap(c.begin(), c.end(), comp); }

Que claramente simplemente reenvía a std::make_heap encima de un objeto c .

Así que abrimos el archivo fuente en vim y encontramos la definición de c :

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

      [...]

      _Sequence  c;

y así concluimos que c es un vector .

Si nos adentramos en los otros métodos, o al inspeccionar la fuente más a fondo, vemos fácilmente que todos los demás métodos de priority_queue también se reenvían a la familia de funciones std::make_heap .

La elección de un montón frente a, por ejemplo, una BST equilibrada, tiene sentido, ya que el tiempo promedio de inserción es menor para el montón, consulte: Árbol de búsqueda binaria (BST)

Answer 6

No hay diferencia en términos de rendimiento. std::priority_queue es solo una clase de adaptador que envuelve el contenedor y la misma llamada a funciones relacionadas con el montón en una clase. La especificación de std::priority_queue establece abiertamente.

Al crear una cola de prioridad basada en el montón a partir de un std::vector expuesto (al llamar directamente a las funciones relacionadas con el montón), se mantiene abierto a la posibilidad de acceso externo, lo que podría dañar la integridad del montón / cola. std::priority_queue actúa como una barrera que restringe el acceso a un mínimo "canónico": push() , pop() , top() etc. Puede verlo como una medida de autodisciplina.

Además, al adaptar su interfaz de cola al conjunto de operaciones "canónicas", lo hace uniforme e intercambiable con otras implementaciones basadas en clases de colas de prioridad que se ajustan a la misma especificación externa.