prioridades - Contenidos de intercambio de colas de prioridad de C++

colas en c++

Question

Estoy escribiendo una clase que tiene tres colas de prioridad como miembros privados.

class Foo {
...
...

private:
  // I am fine with using pointers instead if it helps.
  std::priority_queue<int> first;   // min heap.
  std::priority_queue<int> second;  // max heap.
  std::priority_queue<int> third;  // min heap.
};

Ahora necesito que el first y el third comiencen como min heaps y second como un max heap . Como parte de la funcionalidad de mi clase, necesito hacer lo siguiente:

1. Mueve el second al first . Idealmente, esto se logra a través de la menor cantidad de copias. El vector subyacente solo se debe mover. Además, first debe comportarse como un max heap .
2. Mueve third a second . Esto significa que el second debe comportarse ahora como un min heap .
3. Dado que los contenidos de third se han movido a second , debe estar vacío. Me gustaría asignar un nuevo vector subyacente o reutilizar el first''s vector subyacente (ya no lo necesita más. Además, el tercero ahora debería ser un max heap .

Necesito realizar este ciclo (max -> min y min -> max) un número desconocido de veces.

Estoy luchando para hacer esto con std::priority_queue ya que el Comparador es un argumento de plantilla, lo que significa que no puedo cambiarlo en tiempo de ejecución. Esto me impide convertir un min heap en un max heap .

Así que mis preguntas son:

1. ¿Hay alguna manera de poder doblar std::priority_queue para hacer mi oferta sin hacerlo extremadamente feo?
2. Si no, ¿podría tal vez reestructurar mi clase para hacer lo mismo, pero seguir usando std::priority_queue ?
3. De lo contrario, ¿podría tal vez reutilizar la mayor parte de la lógica de heapify en la biblioteca heapify para lograr esto?

Answer 1

¿Hay alguna manera de poder doblar std :: priority_queue para hacer mi oferta sin hacerlo extremadamente feo?

Podría escribir un envoltorio que oculte el predicado y use la herencia detrás de escena. Sin embargo, eso parece una exageración.

Si no, ¿podría tal vez reestructurar mi clase para hacer lo mismo, pero seguir usando std :: priority_queue?

Podrías envolver el acceso a las colas en funciones. Luego use una variable bool o integer para verificar a qué cola se debe acceder.

De lo contrario, ¿podría tal vez reutilizar la mayor parte de la lógica de heapify en la biblioteca estándar para lograr esto?

Esto suena como la mejor opción, basada en lo que explicaste. Almacene cada priority_queue en un std::vector y use las std::make_heap , std::push_heap y std::pop_heap para administrar la estructura del montón. Si mantiene todas las colas de prioridad en un std::array<std::vector<int>, 3> , puede usar std::rotate para ejecutar la lógica que describió. Además, necesitaría mantener una variable booleana que indique qué predicado usar para las operaciones de almacenamiento dinámico.

Answer 2

Un comparador con el estado.

En realidad, la STL proporciona facilidades para su caso exactamente: Puede pasar un comparador al constructor de la cola de prioridad . La idea clave es dar al comparador algún estado interno que determine si se debe aplicar una operación menor o mayor que . El tipo de comparador se ve así:

struct LessOrGreater
{
    explicit LessOrGreater( bool isLess ) : isLess{isLess} {}

    bool operator()( int lhs, int rhs ) const
    {
        return isLess == (lhs<rhs);
    }

    bool isLess;
};

El tipo real de la cola de prioridad es

using MinOrMaxQueue =
    std::priority_queue<int,std::vector<int>,LessOrGreater>;

La implementación de la clase.

Su clase ahora se puede implementar en términos de esta cola de prioridad especial.

class Foo {
public:
    Foo()
        : first { LessOrGreater{ false } } // initialize as min heap
        , second{ LessOrGreater{ true  } } // initialize as max heap
        , third { LessOrGreater{ false } } // initialize as min heap
    {}

    void op(); // The operation you explained

private:
    MinOrMaxQueue first; 
    MinOrMaxQueue second;
    MinOrMaxQueue third; 
};

Ahora la operación que describiste podría implementarse así:

void Foo::op()
{
    first  = std::move(second);
    second = std::move(third);
    third  = MinOrMaxQueue{ LessOrGreater{ true } }; // might throw!
}

Haciéndolo excepcionalmente seguro

Sin embargo, este código no es seguro para excepciones. Dado que el constructor predeterminado de std::vector<int> podría lanzar (¡el estándar C ++ no garantiza que no fallará aquí!) La tercera línea de la función op() podría lanzar dejando el objeto Foo en un estado no válido. Aquí hay una implementación que es altamente segura para las excepciones y muy probablemente igual de eficiente:

void Foo::op()
{
    MinOrMaxQueue tmp{ LessOrGreater{ true } };
    first .swap( second );
    second.swap( third );
    third .swap( tmp );
}

La primera línea es la única línea que podría lanzar, pero no modifica el objeto Foo . Así que lanzar no puede dañar nada. Las tres líneas restantes nunca se lanzan y, por lo tanto, la función es altamente segura.

Answer 3

Creo que podrías usar aa plain std :: vector como el almacenamiento de datos y luego tener un adaptador para especificar la propiedad del montón. El adaptador mantiene internamente un std :: vector para almacenar los datos y almacena el comparador actual. Déjame ver si esto funciona con tus tres requisitos:

class Heap
{
    Heap& opertor=(Heap&& h)
    {
        swap(*this, h);
        return *this;
    }

    void setComparator( std::function<bool (int, int)> c)
    {
        comparator = std::move(c);
    }

    void insert(int x)
    {
        // use std::push_heap to insert x with current comparator.
    }

    void swap(Heap& h)
    {
        swap(comparator, h.comparator);
        swap(data, h.data);
    }
private:
    std::function<bool (int,int)> comparator;
    std::vector<int> data_;
};

1. Mueve el segundo al primero. Idealmente, esto se logra a través de la menor cantidad de copias. El vector subyacente solo se debe mover. Además, primero debe comportarse como un montón máximo.

Esto se puede hacer llamando first = std::move(second) . Ahora los datos se mueven y el comparador se establece en el de segundo, lo que hace que en primer lugar se convierta en un montón máximo en el futuro.

1. Mueve tercero a segundo. Esto significa que el segundo debe comportarse ahora como un montón mínimo.

Lo mismo que arriba. second = std::move(thid) . El comparador se reinicia y se comportará como un montón mínimo.

1. Dado que los contenidos de tercero se han movido a segundo, debe estar vacío. Me gustaría> asignar un nuevo vector subyacente o reutilizar el primer vector subyacente (ya no lo necesita>. Además, tercero debería ser un montón máximo.

Después de moverse, tercero estará en un estado válido pero indefinido. No puede confiar en que la memoria esté allí, por lo que tendrá que llevarla a un estado válido y definido. Podrías usar third.clear(); third.resize( n ) third.clear(); third.resize( n ) .