Acabo de notar algo y me pregunto si hay alguna razón para eso. A excepción de C ++ (std :: priority_queue es un montón máximo), no conozco ningún otro lenguaje que ofrezca un montón máximo.
El módulo heapq de Python implementa un min-montón dinámico binario en la parte superior de una lista.
La biblioteca de Java contiene una clase PriorityQueue, que implementa una cola de prioridad mínima.
La biblioteca de Go contiene un módulo contenedor / almacenamiento dinámico, que implementa un almacenamiento dinámico mínimo sobre cualquier estructura de datos compatible.
El marco de la Core Foundation de Apple contiene una estructura CFBinaryHeap, que implementa un montón mínimo.
Encuentro un max-heap más intuitivo que un min-heap y creo que técnicamente la diferencia de implementación es solo una cuestión de cambiar un operador de comparación. ¿Hay alguna razón real? ¿La mayoría de las aplicaciones necesitan un mínimo en lugar de un máximo de almacenamiento dinámico? Gracias por adelantado
fuente
std::not2(std::less<T>()).Respuestas:
Como otros han observado, si el montón acepta un comparador, entonces no es demasiado difícil obtener un comportamiento u otro. Sin embargo, una lectura rápida de Google Code sugiere que min-heap es mucho más frecuente en el código real, debido a dos aplicaciones que surgen una y otra vez.
Dijkstra / A * / muchos otros algoritmos de ruta más corta (porque las rutas parciales se alargan).
Simulación de eventos (porque el tiempo avanza).
Además, diría que debido a que la ordenación predeterminada devuelve elementos pequeños a grandes, también debería hacerlo el montón predeterminado.
fuente
Es solo cuestión de gustos. No creo que haya ninguna razón específica. Es como si a algunas personas les gusta expresar problemas de optimización como minimizar costos, mientras que a otros les gusta maximizar las ganancias.
fuente
La mayoría de los idiomas que conozco permiten pasar un parámetro para decidir si debe ser un montón mínimo o máximo. Entonces el valor predeterminado es algo arbitrario. Supongo que para la mayoría de los idiomas es una cuestión de coherencia definir cuál es el operador predeterminado. Para C ++ en el stl, el valor predeterminado
std::lessconduce a un montón mínimo.La coherencia del uso
std::lesspor defecto en todas partes significa que solo tiene que implementar esta comparación cuando está utilizando cualquier tipo de estructura de datos y no tiene que decidir qué estructura de datos utilizará más adelante cuando diseñe sus clases. Supongo que es lo mismo para otros idiomas con la única diferencia de que una comparación mayor que la estándar.fuente
Básicamente, el valor del índice es un número arbitrario. Si cree que el número representa una prioridad, y los números más grandes son prioridades más altas, entonces un montón máximo tiene sentido. Pero si los números representan, por ejemplo, los números conceptuales de panadería ("Tome un número"), entonces min-heap tiene más sentido.
Siempre puede convertir de uno a otro tomando el complemento de 1 del índice.
fuente