algorithm - sucesión - Aplicaciones del mundo real de montones binarios y montones de Fibonacci

sucesion de fibonacci ejercicios

Question

¿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.

Editar: agregó montones binarios también. Curioso saber

Answer 1

En la mayoría de los escenarios, debe elegir según la complejidad de:

• inserción
• encontrar elementos

Y los sospechosos habituales son:

• BST: log(n) insertar y encontrar
• lista enlazada: O(1) insertar y O(n) encontrar
• montón:
  • O(1) inserción
    • promedio para el montón binario, ver: https://.com/a/29548834/895245 )
    • amortizado para Fibonacci. Esto es más fuerte que el promedio, más débil que el peor de los casos.
  • O(1) encuentra solo el primer elemento , O(n) en general
    • el peor caso para el montón binario
    • amortizado por Fibonacci

También está la cola Brodal y otros montones que alcanzan el O(1) peor caso, pero requiere colas aún mayores que las de Fibonacci para valer la pena.

Entonces, si su algoritmo solo necesita "encontrar" el primer elemento y hacer muchas inserciones, los montones son una buena opción.

Como otros mencionaron, este es el caso de Dijkstra.

Answer 2

Las colas de prioridad generalmente se implementan como montones, por ejemplo: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

La computación de los principales N elementos de un gran conjunto de datos se puede hacer de manera eficiente utilizando montones binarios (por ejemplo, las principales consultas de búsqueda en un sitio web a gran escala).

Answer 3

No puedo decir sobre los montones de fibonacci, pero los montones binarios se usan 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.

Answer 4

Raramente usarías 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 operaciones que comienza con una estructura vacía está limitado por los límites indicados anteriormente, algunas (muy pocas) operaciones en la secuencia pueden tardar mucho en completarse (en particular eliminar y eliminar mínimo tener tiempo de ejecución lineal en el peor caso). Por esta razón, los montones de Fibonacci y otras estructuras de datos amortizadas pueden no ser apropiados para los sistemas en tiempo real.

El montón binario es una estructura de datos que se puede usar 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).