Esistono implementazioni di un heap binario standard puramente funzionale? So che ci sono molti heap interessanti, ad esempio: Binomiale, heap di sinistra, tutti hanno un'implementazione funzionale, mi chiedo solo se c'è un modo per implementare l'heap binario standard o dobbiamo usare Array per implementarlo, a causa del tipo immutabile? Grazie!Come posso implementare un heap binario standard puramente funzionale (ocaml o haskell)?
Non è necessario un array per implementare un heap, è possibile implementarlo come struttura ad albero.
data Heap t = Node t (Heap t) (Heap t) | Nil
Lo svantaggio è che si finisce per riallocazione O(log N) dei nodi per ogni operazione heap, e non avrà alcuna della cache località di un'implementazione imperativo basata su array. Alcune operazioni saranno difficili con questa struttura, ma poiché non so cosa vuoi fare con l'heap non posso indicarti una direzione più specifica.
Il motivo per cui abbiamo strutture funzionali speciali come le barrette è di velocizzare operazioni specifiche che normalmente non si eseguono su heap, come il recupero del nodo foglia più a sinistra. Puoi utilizzare molte delle stesse strutture dati che hai appreso per le lingue imperative in Haskell con solo modifiche ai modi in cui sono aggiornate.
Grazie a Dietrich, l'operazione che voglio implementare è far scendere un nuovo valore casuale dalla radice, ma non sono sicuro quale sia il modo migliore per implementare questa operazione in uno stile funzionale. – Ang
Tappo senza vergogna: Braun trees sono candidati perfetti per un min-heap puramente funzionale (o coda di priorità).
È possibile esaminare le idee descritte in questo documento A Functional Approach to Standard Binary Heaps o in questa fonte Heap.scala.
Questa non è una gran domanda. Probabilmente dovresti riformularlo come qualcosa del tipo "Come posso implementare un heap binario puramente funzionale?" - hai molte più probabilità di ottenere risposte utili e perspicaci con questa formulazione. –
@TikhonJelvis grazie – Ang
Questo dipende. Ti aspetti che la versione puramente funzionale utilizzi lo stesso tipo di struttura per i dati? Comportarsi allo stesso modo per determinate operazioni? Se queste cose possono essere diverse, allora può davvero essere chiamato un "mucchio binario"? –