c++ - struttura - min heap




Perché gli heap in c++ sono implementati come algoritmi anziché come contenitori? (4)

Mi chiedevo perché il concetto di heap è implementato come algoritmi ( make_heap , pop_heap , push_heap , sort_heap ) invece di un contenitore. Mi interessa in particolare che la soluzione di qualcuno possa anche spiegare perché set e map sono contenitori anziché raccolte di algoritmi simili (make_set add_set rm_set etc).


Bene, gli heap non sono realmente un contenitore generico nello stesso senso di un set o di una mappa. In genere, si utilizza un heap per implementare un altro tipo di dati astratto. (La più ovvia è una coda di priorità). Sospetto che questa sia la ragione del diverso trattamento.


Gli heap * sono quasi sempre implementati utilizzando un array come struttura dati sottostante. Come tale può essere considerato un insieme di algoritmi che operano sulla struttura dei dati dell'array. Questo è il percorso intrapreso dall'STL durante l'implementazione dell'heap: funzionerà su qualsiasi struttura dati con iteratori ad accesso casuale (array, vettore, deque, ecc.).

Noterai inoltre che il priority_queue di STL richiede un contenitore (che per impostazione predefinita è un vettore). Questo è essenzialmente il tuo contenitore di heap: implementa un heap sulla struttura dati sottostante e fornisce un contenitore wrapper per tutte le operazioni di heap tipiche.

* Binari in particolare. Altre forme di heap (Binomiale, Fibonacci, ecc.) Non lo sono.


Un heap è una struttura dati specifica. I contenitori standard hanno requisiti di complessità ma non specificano in che modo devono essere implementati. È una bella ma importante distinzione. Puoi fare make_heap su diversi contenitori, incluso uno che hai scritto tu stesso. Ma un set o una map significa molto più che un semplice modo di organizzare i dati.

Detto in altri termini, un contenitore standard è più della semplice struttura dati sottostante.


Una ragione ovvia è che è possibile disporre gli elementi come heap in un altro contenitore.
Quindi puoi chiamare make_heap() su un vector o un deque o anche un array C.





heap