Perché sono due concetti diversi entrambi chiamati “cumulo”?

Question

Perché l'heap di runtime utilizzato per l'allocazione dinamica della memoria in linguaggi in stile C e la struttura dei dati entrambi chiamati "mucchio"? C'è qualche relazione?

Answer 1

Donald Knuth dice (The Art of Computer Programming, Terza Ed, Vol 1, pag 435...):

  

Diversi autori hanno cominciato 1975 circa per chiamare il pool di memoria disponibile un "mucchio".

Non dice che gli autori e non dà riferimenti a eventuali documenti specifici, ma non dice che l'uso del termine "cumulo" in relazione alle code di priorità è il senso tradizionale della parola.

Answer 2

Essi hanno lo stesso nome, ma in realtà non sono simili (anche concettualmente). Un mucchio di memoria è chiamato un mucchio nello stesso modo in cui si riferiscono ad un cesto della biancheria come un "mucchio di vestiti". Questo nome viene utilizzato per indicare un luogo piuttosto disordinato dove la memoria può essere allocata e deallocato a volontà. La struttura dei dati (come il link di Wikipedia si fa riferimento fa notare) è molto diversa.

Answer 3

Il nome di collisione è un peccato, ma non è affatto misterioso. Heap è un piccolo, parola comune usato per indicare una pila, collezione, gruppo, ecc L'uso della parola per la struttura dei dati pre-date (sono abbastanza sicuro) il nome del pool di memoria. In realtà, piscina sarebbe stata una scelta molto migliore per questi ultimi, a mio parere. Heap connota una struttura verticale (come una pila), che si inserisce con la struttura di dati, ma non il pool di memoria. Non pensiamo di una memoria-pool mucchio come gerarchico, mentre l'idea fondamentale dietro la struttura di dati è mantenere l'elemento più grande nella parte superiore del mucchio (e sub-cumuli).

Heap la struttura dati risale alla metà degli anni '60; heap il pool di memoria, i primi anni '70. Il termine heap (che significa pool di memoria) è stato utilizzato almeno fin dal 1971 da Wijngaarden nelle discussioni di Algol.

Forse il primo utilizzo di mucchio come una struttura di dati viene trovato sette anni prima in
Williams, J. W. J. 1964. "Algoritmo 232 - Heapsort", Communications of the ACM 7 (6): 347-348

Answer 4

In realtà, leggendo la memoria modo in cui è allocata (vedi compagno Blocchi ) mi ricorda di un cumulo di strutture di dati.

Answer 5

IMO si tratta semplicemente di un incidente / un caso che queste due cose completamente indipendenti hanno lo stesso nome. E 'come grafico e grafico .

Answer 6

struttura dati heap-come viene utilizzato da un algoritmo di trovare allocazione di memoria disponibile. Quanto segue è tratto da http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

  

Quando new viene richiamato, esso inizia a cercare un blocco di memoria libera che si adatta alle dimensioni per la vostra richiesta. Supponendo che un tale blocco di memoria viene trovato, viene contrassegnato come riservato e un puntatore alla posizione che viene restituito. Ci sono diversi algoritmi per ottenere questo risultato, perché un compromesso deve essere fatta tra la scansione di tutta la memoria per trovare il più piccolo blocco libero più grande rispetto alle dimensioni del vostro oggetto, o di ritorno il primo in cui la memoria necessaria si adatta. Al fine di migliorare la velocità di ottenere un blocco di memoria, le aree libere e riservate di memoria sono mantenute in una struttura dati simile ad alberi binari chiamato un mucchio.

Answer 7

I termini colloquiali stack di memoria e la memoria heap non vengono utilizzati nello standard C ++. Lo standard utilizza l'archiviazione statica, stoccaggio filo, memorizzazione automatica e archiviazione dinamica.

Più può essere trovato alla sezione bagagli Duraction dello standard .

Quindi, dalla lingua e punto di libreria standard di vista, non c'è confusione.

Answer 8

Q. Che cosa è un mucchio? A. Un mucchio è una collezione di oggetti immettere sul sopra l'altro.

risposta alla vostra domanda: Sia heap di memoria e heap binario utilizza lo stesso concetto come sapete. I dati sono memorizzati sotto forma di un mucchio nella memoria nello stesso ordine come scritto nel programma che heap binario è una struttura di dati che segue lo stesso concetto di memorizzare dati in modo ordinato in forma di un cumulo (dati in cima dell'altro). Fatemi sapere cosa ne pensate nella sezione commenti.

Answer 9

Forse il primo heap di memoria implementata è stato gestito da una struttura heap?