montón binario vs montón binomial vs montón de fibonacci, con respecto al rendimiento de una cola de prioridad
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Podría alguien explicarme cómo debo decidir si usar una u otra implementación de montón, entre las mencionadas en el título?
Me gustaría una respuesta que me oriente en la elección de la implementación en cuanto al rendimiento de la estructura, según el problema.Ahora mismo, estoy haciendo una cola de prioridad, pero me gustaría saber no solo la implementación más adecuada para este caso, sino los conceptos básicos que me permiten elegir una implementación en cualquier otra situación ...
Otra cosa a considerar es que estoy usando haskell esta vez, así que, si conoces algún truco o algo que pueda mejorar la implementación con este lenguaje, ¡házmelo saber!pero como antes, los comentarios sobre el uso de otros idiomas también son bienvenidos.
¡Gracias!y lo siento si la pregunta es demasiado básica, pero no estoy familiarizado con montones en absoluto.Esta es la primera vez que me enfrento a la tarea de implementar uno ...
¡gracias de nuevo!
Solución
Puede encontrar el tercer artículo en http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf relevante.
Otros consejos
En primer lugar, no implementará un montón estándar en Haskell. En su lugar, implementará un montón persistente y funcional . A veces, las versiones funcionales de las estructuras de datos clásicas son tan eficaces como las originales (por ejemplo, árboles binarios simples), pero a veces no (por ejemplo, colas simples). En el último caso, necesitará una estructura de datos funcional especializada.
Si no está familiarizado con las estructuras de datos funcionales, le sugiero que comience con el excelente libro o tesis (capítulos de interés: al menos 6.2.2, 7.2.2).
Si todo eso se le pasó por la cabeza, le sugiero que comience con la implementación de un simple montón binario vinculado . (Hacer un montón binario eficiente basado en arreglos en Haskell es un poco tedioso). Una vez hecho esto, puede intentar implementar un montón binomial usando el pseudocódigo de Okasaki o incluso comenzando desde cero.
Tienen diferente complejidad de tiempo en diferentes operaciones en Priority Queue. Aquí tienes una tabla visual
╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║ Operation ║ Binary ║ Binomial ║ Fibonacci ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ insert ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ find Min ║ O(1) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Revmove ║ O(logN) ║ O(logN) ║ O(logN) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Decrease Key ║ O(logN) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ║ ║ ║
║ Union ║ O(N) ║ O(logN) ║ O(1) ║
║ ║ ║ ║ ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║ ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║ ║ ■ Heap height = logN ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min. ║
║ ║ ║ ■ Height = k. ║ (keeps find min/max O(1)) ║
║ ║ ║ ■ Degree of root = k. ║ ■ Set of marked nodes. ║
║ Useful ║ ║ ■ Deleting root yields ║ (keep the heaps flat) ║
║ Properties ║ ║ binomial trees ║ ║
║ ║ ║ Bk-1, … , B0. ║ ║
║ ║ ║ (see graph below) ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝
Obtuve esta imagen de las diapositivas de la conferencia de Princeton
Montón binomial:
Montón de Fibonacci:
Nota: Binomial y Fibonacci Heap parecen familiares pero son sutilmente diferentes:
- Montón binomial: consolide árboles con entusiasmo después de cada inserción.
- Montón de Fibonacci: diferir la consolidación de forma perezosa hasta el siguiente mínimo de eliminación.
Algunas referencias al montón Binomial funcional, el montón de Fibonacci y el montón de emparejamiento: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Si el rendimiento es realmente el problema, sugiero usar el montón de emparejamiento.El único riesgo es que su rendimiento sigue siendo una conjetura hasta ahora.Pero los experimentos muestran que el rendimiento es bastante bueno.
