algorithm complessità - Perché gli heap in c++sono implementati come algoritmi anziché come contenitori?




priorità inserimento (5)

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.

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


STL fornisce un heap sotto forma di std :: priority_queue. Le funzioni make_heap, ecc. Sono lì perché hanno degli usi al di fuori del regno della struttura dati stessa (ad esempio l'ordinamento) e per consentire agli heap di essere costruiti sopra strutture personalizzate (come gli array di stack per un "keep the top 10" contenitore).

Per analogia, puoi usare un set std :: set per memorizzare un elenco ordinato, oppure puoi usare std :: sort su un vettore con std :: adjacent_find; std :: sort è il più generale e fa alcune ipotesi sulla struttura dei dati sottostanti.

(Come nota, l'implementazione std :: priority_queue non fornisce effettivamente la propria memoria, per impostazione predefinita crea un vettore std :: come backing store.)


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.


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.


Quando si utilizza new, gli oggetti vengono allocati all'heap. Viene generalmente utilizzato quando prevedi l'espansione. Quando dichiari un oggetto come,

Class var;

è messo in pila.

Dovrai sempre chiamare destroy sull'oggetto che hai posizionato sullo heap con nuovo. Ciò apre il potenziale per perdite di memoria. Gli oggetti posizionati in pila non sono soggetti a perdite di memoria!





c++ algorithm design stl heap