¿Cuáles son las aplicaciones del mundo real de montones de Fibonacci y montones binarios? Sería genial si pudieras compartir alguna instancia cuando la usaste para resolver un problema.Aplicaciones del mundo real de montones binarios y montones de Fibonacci
Edit: Añadido binary heaps también. Curioso saber
Rara vez usaría uno en la vida real. Creo que el objetivo del montón de Fibonacci era mejorar el tiempo de ejecución asintótica del algoritmo de Dijkstra. Puede brindarle una mejora para entradas muy, muy grandes, pero la mayoría de las veces, todo lo que necesita es un simple montón binario.
De wiki:
Aunque el tiempo total de ejecución de una secuencia de de las operaciones a partir de una estructura de vacío está delimitada por las límites dados anteriormente, algunos (muy pocos) operaciones en la secuencia puede tomar muy largo para completar (en particular eliminar y eliminar mínimo tener lineal tiempo de ejecución en el peor de los casos). Para esta razón Fibonacci heaps y otras estructuras de datos amortizadas pueden no ser apropiadas para sistemas en tiempo real.
El montón binario es una estructura de datos que se puede utilizar para encontrar rápidamente el valor máximo (o mínimo) en un conjunto de valores. Se usa en el algoritmo de Dijkstra (ruta más corta), el algoritmo de Prim (árbol de expansión mínimo) y la codificación de Huffman (compresión de datos).
Nota: Fibonacci mejora el tiempo amortizado, no el peor de los casos. Y el montón binario también tiene un promedio de O (1). –
colas de prioridad normalmente se implementan como montones, por ejemplo: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html
Calculando los mejores N elementos de un gran conjunto de datos se puede hacer de manera eficiente utilizando montones binarios (por ejemplo, consultas de búsqueda en un sitio web a gran escala) .
No se puede decir acerca de los montones de fibonacci, pero los montones binarios se utilizan en las colas de prioridad. Las colas de prioridad se usan ampliamente en los sistemas reales. Un ejemplo conocido es la programación de procesos en el kernel. El proceso de mayor prioridad se toma primero. He utilizado las colas de prioridad en la partición de los conjuntos. El conjunto que tiene el número máximo de miembros se debe tomar primero para la partición.
En la mayoría de los casos, usted tiene que elegir en base a la complejidad de:
Y los sospechosos habituales son:
log(n) inserta y encuentraO(1) inserción y O(n) encuentranO(1) inserción
O(1) encuentran para el primer elemento solamente, O(n) en general
Hay también el Brodal queue y otros montones que alcanzan el peor caso de O(1), pero requiere even larger queues que Fibonacci para valer la pena.
Si su algoritmo solo necesita "encontrar" el primer elemento y hacer muchas inserciones, los montones son una buena opción.
Como han mencionado otros, este es el caso de Dijkstra.
Guau, vives y aprendes. Ni siquiera sabía que Fib ... existían montones. Cosas interesantes. – PurplePilot
"Uso del mundo real" parece estar haciendo una pregunta incorrecta, similar a "¿Cuáles son los usos reales de las matrices?" –
¡Todos conocen el uso real de las matrices! – devnull