heap binario vs heap binomiale vs heap di fibonacci, per quanto riguarda le prestazioni per una coda prioritaria
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Qualcuno potrebbe spiegarmi come dovrei decidere se utilizzare l'una o l'altra implementazione dell'heap, tra quelle menzionate nel titolo?
Vorrei una risposta che mi guidasse nella scelta dell'implementazione rispetto alle prestazioni della struttura, in base al problema.In questo momento, sto facendo una coda prioritaria, ma vorrei conoscere non solo l'implementazione più appropriata per questo caso, ma le basi che mi consentono di scegliere un'implementazione in qualsiasi altra situazione ...
Un'altra cosa da considerare è che sto usando haskell questa volta, quindi, se conosci qualche trucco o qualcosa che potrebbe migliorare l'implementazione con questo linguaggio, fammelo sapere!ma come prima, anche i commenti sull'uso di altre lingue sono ben accetti!
Grazie!e scusa se la domanda è troppo elementare, ma non ho affatto familiarità con gli heap.Questa è la prima volta che devo affrontare il compito di implementarne uno ...
grazie ancora!
Soluzione
Potresti trovare il terzo articolo in http://themonadreader.files.wordpress.com / 2010/05 / issue16.pdf pertinenti.
Altri suggerimenti
Prima di tutto, non implementerai un heap standard in Haskell. Invece, implementerai un heap persistente e funzionale . A volte le versioni funzionali delle strutture dati classiche sono performanti come l'originale (ad esempio semplici alberi binari) ma a volte no (ad esempio semplici code). In quest'ultimo caso avrai bisogno di una struttura dati funzionale specializzata.
Se non hai familiarità con le strutture dati funzionali, ti suggerisco di iniziare con il fantastico book o tesi (capitoli di interesse: almeno 6.2.2, 7.2.2).
Se tutto questo ti è passato per la testa, ti suggerisco di iniziare con l'implementazione di un semplice heap binario collegato . (Creare un heap binario efficiente basato su array in Haskell è un po 'noioso.) Una volta fatto, potresti provare a implementare un heap binomiale usando lo pseudo codice di Okasaki o anche partendo da zero.
Hanno una complessità temporale diversa su operazioni diverse sulla coda prioritaria. Ecco una tabella visiva per te
╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║ 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) ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝
Ho preso questa immagine dalle diapositive di Princeton
Binomial Heap:
Fibonacci Heap:
Nota: Binomial e Fibonacci Heap sembrano familiari ma sono leggermente diversi:
- Heap binomiale: consolida con entusiasmo gli alberi dopo ogni inserimento.
- Fibonacci heap: rimanda pigramente il consolidamento fino alla successiva cancellazione-min.
Alcuni riferimenti a heap binomiale funzionale, heap di Fibonacci e heap di accoppiamento: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
Se il problema è davvero le prestazioni, suggerisco di utilizzare l'heap di accoppiamento.L'unico rischio è che le sue prestazioni siano ancora una congettura fino ad ora.Ma gli esperimenti dimostrano che le prestazioni sono abbastanza buone.
