L'heap è effettivamente un heap?

Question

Possibili duplicati:
Why are two different concepts both called “heap”?
What's the relationship between “a” heap and “the” heap?

In .NET (e Java per quanto ne so), l'area in cui gli oggetti sono allocati dinamicamente viene indicato come l'heap gestito . Tuttavia, la maggior parte dello documentation descrive come funziona l'heap gestito come una struttura di dati lineare, ad esempio un elenco o uno stack collegato.

Quindi, è l'heap gestito in realtà un heap, o è implementata con qualche altra struttura di dati? Se in realtà non utilizza una struttura dati dell'heap, sembra un significativo fallimento della terminologia per sovraccaricare il significato di questa parola.

Se è infatti una struttura heap, qual è il valore che soddisfa la proprietà mucchio: la dimensione della regione di memoria allocata?

Answer 1

No, il cumulo non è un heap-ordered binomial tree a tutti. Non è chiaro (per me) di chi sia la colpa dello scontro terminologico, ma entrambi gli usi del cumulo risalgono a decenni fa (metà 1970, sembra). Parte della storia è discussa in this article.

Answer 2

io non sono sicuro che la mia risposta, ma per quanto ne so in linguaggi come C# o Java, dove la memoria è gestita mia Garbage Collector della regione di memoria non è lineare. Il GC libera la memoria che può liberare e quando la memoria è bassa compatta la memoria eseguendo una sorta di deframmentazione. Sposta i blocchi di memoria che il programma usa per creare uno spazio nella "fine". Perché hai bisogno di questa risposta? Vuoi creare una gestione della memoria di basso livello?

Answer 3

In questo senso, "heap" significa: un'area di memoria speciale utilizzata per memorizzare importanti risorse. In quel contesto non è correlato alla "struttura dei dati dell'heap".

Answer 4

Certamente non ho la conoscenza storica per commentare questo con qualsiasi autorità, ma credo che il termine "heap" come impiegato per descrivere il meccanismo di allocazione della memoria per oggetti a vita più lunga in .NET e Java sia più inteso come una parola evocativa e descrittiva, questa grande massa di memoria non strutturata (dal punto di vista dello sviluppo) in cui le cose vivono. Lo "stack" in contrasto evoca l'immagine di una regione di dati molto più strutturata (di nuovo, dal punto di vista dello sviluppatore): "dove" le cose vivono nello stack si sente molto più rilevante di "dove" vivono sul mucchio.

Questo è chiaramente molto diversa da quella attuale heap data structure, che usa la parola "cumulo" per fare riferimento alla cosiddetta proprietà di heap (da Wikipedia):

se B è un nodo figlio di A, quindi il tasto (A) ≥ (B).

Quindi sì, in realtà non sono correlati. Uno è solo un termine descrittivo mentre l'altro ha una definizione molto più formale.