C ++ 11 (o C ++ 14?) Implementación máxima del montón con un ejemplo simple -- ++ campo con c++11 campo con c++14 campo con heap camp codereview Relacionados El problema

C++11 (or C++14?) max heap implementation with a simple example


7
vote

problema

Español

He estado escribiendo C ++ 03 no profesionalmente durante mucho tiempo, y finalmente comencé a jugar con C ++ 11 y C ++ 14. Decidí probar mi mano en la implementación de una estructura de datos que antes estaba desconocida con: un montón máximo.

  #include <iostream> #include <vector> #include <string> #include <stdexcept>  template<typename T, typename C> class Heap { private:      std::vector<T> items;     C compare;      // Heap operations.     void heapify(size_t root = 0);     void siftDown(size_t node);     void siftUp(size_t node);      // Utilities to retrieve parent, left, and right node indices.     constexpr size_t parent(size_t node) const;     constexpr size_t left(size_t parent) const;     constexpr size_t right(size_t parent) const;  public:      Heap(C compare = C()): compare{compare} {}     Heap(const std::vector<T>& items, C compare = C()): items{items}, compare{compare} { heapify(); };     Heap(std::vector<T>&& items, C compare = C()): items{items}, compare{compare} { heapify(); }     template<typename Iterator>     Heap(Iterator begin, Iterator end, C compare = C()): items{begin, end}, compare{compare} { heapify(); };     Heap(const Heap&) = default;     Heap(Heap&&) = default;     ~Heap() = default;     Heap& operator=(const Heap&) = default;     Heap& operator=(Heap&&) = default;      void push(const T& item);     T pop();     const T& top() const;      const T& item(size_t node) const;     constexpr size_t size() const; };  // Heapify an unordered array in O(N). This can also be done in O(N log N) using repeated insertions. template<typename T, typename C> void Heap<T, C>::heapify(size_t root) {     if (root >= size()) return;      size_t l = left(root), r = right(root);      heapify(l);     heapify(r);      siftDown(root); }  // Sift an item down in O(log N). template<typename T, typename C> void Heap<T, C>::siftDown(size_t node) {     size_t l = left(node), r = right(node);      // Find which item should be highest between this one and its children.     size_t higher = node;     if (l < size() && compare(items[l], items[higher])) higher = l;     if (r < size() && compare(items[r], items[higher])) higher = r;      // If one of its children should be higher, swap and continue to sift down.     if (higher != node)     {         std::swap(items[node], items[higher]);         siftDown(higher);     } }  // Sift an item up in O(log N). template<typename T, typename C> void Heap<T, C>::siftUp(size_t node) {     if (node == 0 || node >= size()) return;      const size_t p = parent(node);      // If this item should be higher than its parent, swap and continue to sift up.     if (compare(items[node], items[p]))     {         std::swap(items[node], items[p]);         siftUp(p);     } }  template<typename T, typename C> constexpr size_t Heap<T, C>::parent(size_t node) const {     return node > 0 ? (node - 1) / 2 : node; }  template<typename T, typename C> constexpr size_t Heap<T, C>::left(size_t parent) const {     return parent * 2 + 1; }  template<typename T, typename C> constexpr size_t Heap<T, C>::right(size_t parent) const {     return parent * 2 + 2; }  template<typename T, typename C> void Heap<T, C>::push(const T& item) {     // Insert as the last item.     items.push_back(item);      // Sift it up to re-establish heap property.     siftUp(size() - 1); }  template<typename T, typename C> T Heap<T, C>::pop() {     if (size() == 0) return T();      T ret{top()};      // Move last item to the top, then reduce the array size by one.     items[0] = items[size() - 1];     items.pop_back();      // Sift this new top item down to re-establish heap property.     siftDown(0);      return ret; }  template<typename T, typename C> const T& Heap<T, C>::top() const {     return items.front(); }  template<typename T, typename C> const T& Heap<T, C>::item(size_t node) const {     return items[node]; }  template<typename T, typename C> constexpr size_t Heap<T, C>::size() const {     return items.size(); }  template<typename T, typename C> void print(std::ostream& stream, const Heap<T, C>& h, size_t root = 0, size_t level = 0) {     if (root >= h.size()) return;      // Print left child.     print(stream, h, root * 2 + 1, level + 1);      stream << std::string(level * 4, ' ') << h.item(root) << " ";      // Print right child.     print(stream, h, root * 2 + 2, level + 1); }  template<typename T, typename C> std::ostream& operator<<(std::ostream& stream, const Heap<T, C>& h) {     print(stream, h);     return stream; }  int main() {     Heap<int, std::greater<int>> h;     std::vector<int> arr;      for (int i = 0; i < 10; ++i)     {         int x = rand() % 20;         h.push(x);         arr.push_back(x);     }      Heap<int, std::greater<int>> h2{arr.begin(), arr.end()};      std::cout << "Created via push(): " << h;     std::cout << "Created via heapify(): " << h2;      std::cout << "Popping top item..." << std::endl;      h.pop();     h2.pop();      std::cout << "Created via push(): " << h;     std::cout << "Created via heapify(): " << h2; }   

En busca de comentarios sobre: ​​

  • ¿Estoy usando características C ++ 11/14 correctamente? ¿He escrito algo que sea redundante? ¿Falta algo importante?
  • es mi implementación de MAX MOAP? ¿Es mi horario de análisis de complejidad (vea los comentarios anteriores de las implementaciones)?
  • ¿He seguido las mejores prácticas para implementar un contenedor genérico con una función de comparación personalizada?
  • ¿He cometido errores con respecto a la seguridad de excepción?

Aparte de eso, siéntase libre de destruir completamente el código. Dame sus pensamientos honestos como si estuviera revisando el checkin de un compañero de trabajo (e ignore el hecho de que si yo fuera su compañero de trabajo, solo usaría std::priority_queue en su lugar).

Original en ingles

I've been writing C++03 non-professionally for a long time, and I finally started to play around with C++11 and C++14. I decided to try my hand at implementing a data structure that I was previously unfamiliar with: a max heap.

#include <iostream> #include <vector> #include <string> #include <stdexcept>  template<typename T, typename C> class Heap { private:      std::vector<T> items;     C compare;      // Heap operations.     void heapify(size_t root = 0);     void siftDown(size_t node);     void siftUp(size_t node);      // Utilities to retrieve parent, left, and right node indices.     constexpr size_t parent(size_t node) const;     constexpr size_t left(size_t parent) const;     constexpr size_t right(size_t parent) const;  public:      Heap(C compare = C()): compare{compare} {}     Heap(const std::vector<T>& items, C compare = C()): items{items}, compare{compare} { heapify(); };     Heap(std::vector<T>&& items, C compare = C()): items{items}, compare{compare} { heapify(); }     template<typename Iterator>     Heap(Iterator begin, Iterator end, C compare = C()): items{begin, end}, compare{compare} { heapify(); };     Heap(const Heap&) = default;     Heap(Heap&&) = default;     ~Heap() = default;     Heap& operator=(const Heap&) = default;     Heap& operator=(Heap&&) = default;      void push(const T& item);     T pop();     const T& top() const;      const T& item(size_t node) const;     constexpr size_t size() const; };  // Heapify an unordered array in O(N). This can also be done in O(N log N) using repeated insertions. template<typename T, typename C> void Heap<T, C>::heapify(size_t root) {     if (root >= size()) return;      size_t l = left(root), r = right(root);      heapify(l);     heapify(r);      siftDown(root); }  // Sift an item down in O(log N). template<typename T, typename C> void Heap<T, C>::siftDown(size_t node) {     size_t l = left(node), r = right(node);      // Find which item should be highest between this one and its children.     size_t higher = node;     if (l < size() && compare(items[l], items[higher])) higher = l;     if (r < size() && compare(items[r], items[higher])) higher = r;      // If one of its children should be higher, swap and continue to sift down.     if (higher != node)     {         std::swap(items[node], items[higher]);         siftDown(higher);     } }  // Sift an item up in O(log N). template<typename T, typename C> void Heap<T, C>::siftUp(size_t node) {     if (node == 0 || node >= size()) return;      const size_t p = parent(node);      // If this item should be higher than its parent, swap and continue to sift up.     if (compare(items[node], items[p]))     {         std::swap(items[node], items[p]);         siftUp(p);     } }  template<typename T, typename C> constexpr size_t Heap<T, C>::parent(size_t node) const {     return node > 0 ? (node - 1) / 2 : node; }  template<typename T, typename C> constexpr size_t Heap<T, C>::left(size_t parent) const {     return parent * 2 + 1; }  template<typename T, typename C> constexpr size_t Heap<T, C>::right(size_t parent) const {     return parent * 2 + 2; }  template<typename T, typename C> void Heap<T, C>::push(const T& item) {     // Insert as the last item.     items.push_back(item);      // Sift it up to re-establish heap property.     siftUp(size() - 1); }  template<typename T, typename C> T Heap<T, C>::pop() {     if (size() == 0) return T();      T ret{top()};      // Move last item to the top, then reduce the array size by one.     items[0] = items[size() - 1];     items.pop_back();      // Sift this new top item down to re-establish heap property.     siftDown(0);      return ret; }  template<typename T, typename C> const T& Heap<T, C>::top() const {     return items.front(); }  template<typename T, typename C> const T& Heap<T, C>::item(size_t node) const {     return items[node]; }  template<typename T, typename C> constexpr size_t Heap<T, C>::size() const {     return items.size(); }  template<typename T, typename C> void print(std::ostream& stream, const Heap<T, C>& h, size_t root = 0, size_t level = 0) {     if (root >= h.size()) return;      // Print left child.     print(stream, h, root * 2 + 1, level + 1);      stream << std::string(level * 4, ' ') << h.item(root) << "\n";      // Print right child.     print(stream, h, root * 2 + 2, level + 1); }  template<typename T, typename C> std::ostream& operator<<(std::ostream& stream, const Heap<T, C>& h) {     print(stream, h);     return stream; }  int main() {     Heap<int, std::greater<int>> h;     std::vector<int> arr;      for (int i = 0; i < 10; ++i)     {         int x = rand() % 20;         h.push(x);         arr.push_back(x);     }      Heap<int, std::greater<int>> h2{arr.begin(), arr.end()};      std::cout << "Created via push():\n" << h;     std::cout << "Created via heapify():\n" << h2;      std::cout << "Popping top item..." << std::endl;      h.pop();     h2.pop();      std::cout << "Created via push():\n" << h;     std::cout << "Created via heapify():\n" << h2; } 

Mainly looking for feedback on:

  • Am I using C++11/14 features correctly? Have I written anything that's redundant? Am I missing anything important?
  • Is my max heap implementation correct? Is my time complexity analysis (see comments above implementations) correct?
  • Have I followed best practices in implementing a generic container with a custom comparison function?
  • Have I made any mistakes with regards to exception safety?

Aside from that, please feel free to completely rip the code apart. Give me your honest thoughts as if you're reviewing a coworker's checkin (and ignore the fact that if I was your coworker, I would just use std::priority_queue instead).

           

Lista de respuestas

6
 
vote
vote
La mejor respuesta
 

Mover Constructor

error común aquí. Pensarías que los artículos serían una referencia de valor R; pero no lo es. Recuerde "Los objetos nombrados" nunca son las referencias de valor R, el n4 solo marca el sitio de enlace para una referencia de valor R.

  n5  

Cuando pasa este valor a "Artículos", debe volver a crear la referencia de valor R.

  n6  

Tienes el constructor de movimiento. Entonces, ¿por qué solo tienes un pulsador de copia?

  n7  

esperaría un empuje de movimiento.

  n8  

Los contenedores estándar (que admiten POP ()) devuelven un tipo n9 . Esto se debe a que no existe una manera de implementar una excepción segura mean0 que devuelve un valor. Por eso también tienen mean1 . Para que pueda obtener el valor con mean2 . Luego haga una excepción segura mean3 .

  mean4  

Así que definiría la interfaz como esta:

  mean5  

Si está proporcionando un accesero genérico:

  mean6  

Entonces, ¿por qué no proporcionar mean7 ? No estoy seguro de que sea una buena idea. Pero es una pregunta que deberías preguntar y responder por ti mismo.

Estilo

Revise su guía de estilo local. Personalmente, no me gusta esto, ya que creo que hace que el 99887766555443398 sea más difícil de leer. Pero su guía puede permitirlo.

  mean9  

Me gustaría haber visto:

  summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n)                   then (e i + summation (i+1) n e)                   else (e i) 00  

una línea por declaración;

  summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n)                   then (e i + summation (i+1) n e)                   else (e i) 01  

El código se supone que es legible humano. Prefiero poner una declaración por línea. Hace que el código sea más fácil de leer y analizar un mantenedor.

También prefiere usar nombres de identificadores significativos. Si realiza una búsqueda de summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n) then (e i + summation (i+1) n e) else (e i) 02 o summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n) then (e i + summation (i+1) n e) else (e i) 03 , obtendrá muchos positivos falsos al buscar su código (especialmente si su código tiene comentarios).

  summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n)                   then (e i + summation (i+1) n e)                   else (e i) 04  

Preguntas de comentarios:

1) ¿Debo usar automáticamente en todas partes, como Const Auto LeftIndex = ...? ¿Qué pasa con Const para todo lo que no cambia?

No lo creo. Lo principal de C ++ es su fuerte mecanografía. Pero también debe preocuparse por la capacidad de los compiladores para cambiar los tipos (moldes insertados del compilador (flotador = & gt; int etc), o el uso del constructor de argumento único para convertir).

Personalmente, uso tipos específicos donde sea que necesite un tipo específico; Pero uso automático cuando no me importa el tipo (los iteradores son un gran ejemplo aquí; No me importa el tipo real que me importa el comportamiento).

2) ¿Debo usar la semántica de movimiento para comparar los constructores?

No lo creo. Usted compara el tipo debe ser relativamente ligero (de hecho, dudo que haya muchos casos de uso donde el objeto de cuidado tiene algún miembro).

3) ¿Incluso necesito STD :: Vector & amp; & amp; ¿Artículos en el constructor? ¿Por qué no solo Std :: Artículos vectoriales, deja que el constructor de STD: FOO {STD :: Mover (Sententaitems)} Llame, y luego use STD :: Mover nuevamente dentro del constructor de montón?

eres correcto. Usted podría tener un parámetro normal.

Preguntas desde arriba:

En busca de comentarios sobre: ​​

¿Estoy usando características C ++ 11/14 correctamente? ¿He escrito algo que sea redundante? ¿Falta algo importante?

Aparte de usted error con la construcción de movimiento del vector de entrada se ve bien.

¿Es correcta mi implementación de MAX MOAP? ¿Es el análisis de complejidad de mi tiempo (vea los comentarios anteriores de las implementaciones)?

se ve bien.

¿He seguido las mejores prácticas para implementar un contenedor genérico con una función de comparación personalizada?

no realmente. Le faltan un montón de funcionalidad si desea llamar a esto un contenedor. Consulte: concepto: contenedor . pero No creo que necesite llamar a su estructura un contenedor es un 998877766554433105 Al igual que a summation :: (Integral a, Fractional b) => a -> a -> (a -> b) -> b summation i n e = if (i < n) then (e i + summation (i+1) n e) else (e i) 06

¿Han cometido errores con respecto a la seguridad de excepción?

Dado que no realiza ninguna administración de recursos (y delegue todo el trabajo a STD :: ector) probablemente estás bien.

 

Move constructor

Common mistake here. You would think that items would be an R-Value reference; but its not. Remember "named" objects are never R-Value references the && just marks the binding site for an R-Value reference.

    Heap(std::vector<T>&& items, C compare = C())         : items{items}     // This will bind to the std::vector(std::vector const&)         , compare{compare}     { heapify(); } 

When you pass this value to "items" you need to create the R-Value reference again.

    Heap(std::vector<T>&& items, C compare = C())         : items{std::move(items)}     // This will bind to the std::vector(std::vector&&)         , compare{compare}     { heapify(); } 

You have the move constructor. So why do you only have a copy push?

    void push(const T& item); 

I would expect a move push.

    void push(T&& item);  

The standard containers (that support pop()) return a void type. This is because there is not a way to implement an exception safe pop() that returns a value. That is also why they have top(). So you can get the value with top(). Then do an exception safe pop().

    T pop();     const T& top() const; 

So I would define the interface like this:

    void pop();     const T& top() const; 

If you are providing a generic accesser:

    const T& item(size_t node) const; 

Then why not provide operator[](size_t node)? Not sure it is a good idea. but it is a question you should ask and answer for yourself.

Style

Check your local style guide. I personally don't like this as I think it makes the if statement harder to read. But your guide may allow it.

    if (root >= size()) return; 

I would like to have seen:

    if (<cont>) {  // Always put braces on if statements.         return;    // Always new line and indent for the sub block.     } 

One Line per declaration;

    size_t l = left(root), r = right(root); 

The code is suposed to be human readable. Prefer to put one declaration per line. It makes the code easier to read and parse for a maintainer.

Also prefer to use meaningful identifier names. If you do a search for l or r then you are going to get a lot of false positives when searching your code (especially if your code has comments).

    size_t leftIndex  = left(root);  // Not that hard.     size_t rightIndex = right(root); // easier to search for. 

Questions from comments:

1) Should I just use auto everywhere, like const auto leftIndex = ...? What about const for everything that doesn't change?

I don't think so. The main thing about C++ is its strong typing. But you also need to worry about the compilers ability to change types (compiler inserted casts (float => int etc), or use of single argument constructor to convert).

Personally I use specific types wherever I need a specific type; but I use auto when I don't care about the type (Iterators are a great example here; I don't care about the actual type I care about the behavior).

2) Should I use move semantics for compare in the constructors?

I don't think so. You compare type should be relatively light weight (in fact I doubt there are many use cases where the care object has any members).

3) Do I even need std::vector&& items in the constructor? Why not just std::vector items, let the std::vector constructor do a move for the Heap<...> foo{std::move(existingItems)} call, and then use std::move again inside the Heap constructor?

You are correct. You could have a normal parameter.

Questions from above:

Mainly looking for feedback on:

Am I using C++11/14 features correctly? Have I written anything that's redundant? Am I missing anything important?

Apart from you mistake with the move construction of the input vector it looks fine.

Is my max heap implementation correct? Is my time complexity analysis (see comments above implementations) correct?

Looks OK.

Have I followed best practices in implementing a generic container with a custom comparison function?

Not really. You are missing a whole bunch of functionality if you wish to call this a container. See: Concept: Container. BUT I don't think you need to call your structure a container it is a Container Adapter just like a std::priority_queue

Have I made any mistakes with regards to exception safety?

Since you don't do any resource management (and delegate all the work to std::vector) you are probably fine.

 
 
         
         
4
 
vote

con respecto a "mejores prácticas" , le recomendaría revisar el pautas básicas de C ++ para sugerencias como:

  • "Si su función no puede tirar, declararlo no Excepto". Esto parece un consejo especialmente aplicable para el código de la biblioteca.
  • "Use const para definir objetos con valores que no cambien después de la construcción". Noté que las variables como l Heap<T, C>::heapify(size_t root) no estaba haciendo esto.
  • "Use Auto para evitar la repetición redundante de los nombres de tipo". auto3 También requiere que las variables se inicien, lo que puede evitar un codificador que está cambiando su código de olvidarse accidentalmente para inicializar un valor. El uso también parece ser útil para el código de plantilla donde los tipos pueden ser más fluidos para comenzar y noté que la variable 99887766655544334 se declara siempre como tipo size_t (en lugar de 'Auto 'o' Const Auto ').

con respecto a la falta de algo importante:

  • Tal vez la situación hipotética de cuándo std::numeric_limits<size_t>::max() / 2 Se han empujado a su contenedor. Suponiendo que la memoria no se hubiera agotado antes de eso, parece que estaría recibiendo la semántica en este momento. Tanto el parent * 2 + 1 99887766555433877665544338 Se envolverían y sospeche 9988777665544339 tendría un problema. Si nada más, parece razonable documentar esta limitación (asumiendo que soy correcto).
 

Regarding "best practices", I'd recommend checking out the C++ Core Guidelines for suggestions like:

  • "If your function may not throw, declare it noexcept". This seems like especially applicable advice for library code.
  • "Use const to define objects with values that do not change after construction". I noticed that variables like l in Heap<T, C>::heapify(size_t root) wasn't doing this.
  • "Use auto to avoid redundant repetition of type names". auto also requires variables to be initialized which may prevent a coder who is changing your code from accidentally forgetting to initialize a value. It's usage also seems helpful for template code where the types may be more fluid to begin with and I noticed that the l variable is always declared as type size_t (instead of 'auto' or 'const auto').

Regarding missing anything important:

  • Perhaps the hypothetical situation of when std::numeric_limits<size_t>::max() / 2 items have been pushed into your container. Assuming memory hadn't been exhausted before then, it looks like you'd be getting mod wrap semantics at this point. Both the parent * 2 + 1 or parent * 2 + 2 operations would wrap around and I suspect siftDown would have a problem. If nothing else, it seems reasonable to document this limitation (assuming I'm correct).
 
 

Relacionados problema

6  Implementación de D-Ary MAX MAIL  ( D ary max heap implementation ) 
Implementé un montón de D-Ary Max respaldado por un vector para el cambio de tamaño. Me gustaría conocer las posibles mejoras en el rendimiento, el diseño y e...

4  Min montón de implementación de árboles en Python 3  ( Min heap tree implementation in python 3 ) 
Escribí un montón de minuto con un árbol binario. ¿Cómo puedo mejorar la complejidad del tiempo de insertar y eliminar la función para ser $ mathcal {o} (l...

8  Implementación de minheap  ( Minheap implementation ) 
Por favor comente sobre esto. class MinHeap<T> where T: IComparable { List<T> elements; public MinHeap() { element...

5  A * Search Algorithm: Abra el juego y el montón  ( A search algorithm open set and heap ) 
Estoy trabajando en una implementación de algoritmo de búsqueda A * y esto es lo que acumulé para la lista abierta: from heapq import heappush, heappop cl...

3  Implementación del montón en C #  ( Heap implementation in c ) 
Estoy aprendiendo estructuras de datos fundamentales, y quiero saber si esta es una implementación válida de un montón. ¿Se pueden usar cualquier característi...

1  Encontrar la mediana de funcionamiento con 2 montones [cerrado]  ( Finding the running median with 2 heaps ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

2  Montón Binomial en Java  ( Binomial heap in java ) 
Tengo esta implementación de un montón de binomio que proporciona inserto, disminución de la tecla y el extracto en el tiempo logarítmico. minpriorityqueue...

3  Implementación del montón de N-Ary  ( N ary heap implementation ) 
NaryHeap Como generalización del montón binario. Cada nodo tiene hasta n niños. También se da una especialización de plantillas para n = 2 ( BinaryHeap3 ). ...

17  C # implementación de trajes  ( C treap implementation ) 
Recientemente desarrollé un simple trate estructura de datos en C #. En el futuro, puedo tener la clase extender IDictionary . Por ahora, solo expongo un a...

6  Optimización de la implementación de Dijkstra utilizando PriorityQueue en Java  ( Optimizing dijkstra implementation using priorityqueue in java ) 
Estoy tratando de hacer que la implementación de Dijkstra sea más eficiente. A continuación se muestra el código para la clase {% for tasks in tasks %} <...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos