¿Hay implementaciones de un montón binario estándar puramente funcional? Sé que hay montones de montones interesantes, por ejemplo: binomial, de izquierda, todos tienen implementación funcional, solo me pregunto si hay alguna manera de implementar un montón binario estándar o si tenemos que usar Array para implementarlo, debido al tipo inmutable. ¡Gracias!¿Cómo puedo implementar un montón binario estándar puramente funcional (ocaml o haskell)?
No necesita una matriz para implementar un montón, puede implementarlo como una estructura de árbol.
data Heap t = Node t (Heap t) (Heap t) | Nil
El inconveniente es que se termina la reasignación O(log N) de los nodos para cada operación de lixiviación, y no tendrá ninguna de la localidad caché de una aplicación imperativa basada en matrices. Algunas operaciones serán difíciles con esta estructura, pero como no sé qué quieres hacer con el montón, no puedo señalarte en una dirección más específica.
La razón por la que tenemos estructuras funcionales especiales como árboles de dedo es para acelerar operaciones específicas que normalmente no se realizan en montones, como recuperar el nodo de la hoja más a la izquierda. Puede usar muchas de las mismas estructuras de datos que aprendió para lenguajes imperativos en Haskell con solo cambios en las formas en que se actualizan.
Gracias a Dietrich, la operación que deseo implementar es presionar un nuevo valor aleatorio desde la raíz, pero no estoy seguro de cuál es la mejor manera de implementar esta operación en un estilo funcional. – Ang
Conector Shameless: Braun trees son candidatos perfectos para un min-heap puramente funcional (o cola de prioridad).
Puede consultar las ideas descritas en este documento A Functional Approach to Standard Binary Heaps o en esta fuente Heap.scala.
Esto no es realmente una gran pregunta. Probablemente debería reformularlo como algo así como "¿Cómo puedo implementar un montón binario puramente funcional?": Es mucho más probable que obtenga respuestas útiles e intuitivas con esta formulación. –
@TikhonJelvis gracias – Ang
Eso depende. ¿Esperas que la versión puramente funcional use el mismo tipo de estructura para los datos? ¿Comportarse de la misma manera para ciertas operaciones? Si se permite que estas cosas sean diferentes, ¿se puede llamar realmente un "montón binario"? –