Por que dois conceitos diferentes são chamados de "heap"?

170

Por que o heap de tempo de execução é usado para alocação dinâmica de memória em linguagens no estilo C e a estrutura de dados é chamada de "heap"? Existe alguma relação?

c++ heap terminology heap-memory Andrey Fedorov
fonte
4
Eu estava pensando isso hoje, enquanto estudava estruturas de dados.
MitMaro
1
pergunta duplicada? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Vá para um dicionário de inglês e conte o número de entradas em "Executar". Quantas das mais de 40 entradas se aplicam aos computadores? :)
jmucchiello
2
possível duplicata de Qual é a relação entre "um" heap e "the" heap?
RCIX
Um post relacionado aqui heap de tempo de execução wrt usado para alocação de memória dinâmica.
RBT

Respostas:

77

Donald Knuth diz (The Art of Computer Programming, Terceira Ed., Vol. 1, p. 435):

Vários autores começaram por volta de 1975 a chamar o pool de memória disponível de "pilha".

Ele não diz quais autores e não faz referência a nenhum artigo específico, mas diz que o uso do termo "pilha" em relação às filas prioritárias é o sentido tradicional da palavra.

James McNellis
fonte
11
Pool seria um nome melhor que heap.
7
Interessante. Alguém deve perguntar se ele se lembra de quais autores.
Prof. Falken
27
A Wikipedia afirma que é porque, numa fase inicial, o Lisp usou uma pilha (estrutura de dados) para implementar seu armazenamento de memória. Não diz como. Sua referência é "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introdução aos algoritmos. MIT Press / McGraw-Hill.", Que eu não tenho.
21712 Steve Steveop
2
Não tenho referência para isso, mas meu palpite seria que, inicialmente, a estrutura de dados usada para organizar referências para abrir blocos de memória era uma pilha mínima. Parece que seria pelo menos uma maneira decente de encontrar rapidamente o menor bloco de memória que permitiria armazenar os dados que você estava tentando armazenar. Atualização: O que eu disse soa exatamente como blocos de amigos pt.wikipedia.org/wiki/Dynamic_memory_allocation # Buddy% 5Fblocks
será
4
@SteveJessop - Verificando Cormen, Leiserson, Rivest, Stein - 3ª edição (2009) no início do capítulo Heapsort, apenas diz 'O termo "heap" foi originalmente cunhado no contexto de heapsort, mas desde então se refere a " armazenamento coletado pelo lixo ", como as linguagens de programação que Java e Lisp fornecem. Nossa estrutura de dados de heap não é um armazenamento coletado por lixo e, sempre que nos referirmos a pilhas neste livro, queremos dizer uma estrutura de dados em vez de um aspecto da coleta de lixo. ' O CLRS - 2ª edição também possui quase o mesmo fraseado (nenhuma indicação de que o Lisp usou um Heap).
dr jimbob
64

Eles têm o mesmo nome, mas na verdade não são parecidos (mesmo conceitualmente). Uma pilha de memória é chamada de pilha da mesma maneira que você chamaria um cesto de roupa suja como uma "pilha de roupas". Esse nome é usado para indicar um local um pouco confuso onde a memória pode ser alocada e desalocada à vontade. A estrutura de dados (como o link da Wikipedia que você faz referência) é bem diferente.

Andrew Hare
fonte
8
Sim, acho que esse é o ponto em que ele está baseando sua pergunta: são diferentes. Então, por que eles são chamados da mesma coisa - existe alguma relação subjacente.
9139 Sean Owen
9
A maneira como interpretei essa resposta é "não, não há relação subjacente", por isso responde à pergunta.
Laurence Gonsalves
Andrew está respondendo isso. Não há relação. Apenas uma coincidencia. A pilha de memória é mais fiel ao uso comum, pois a memória é alocada como se fosse uma "pilha de roupas". A estrutura de dados, no entanto, exigia uma maior extensão de imaginação. E isso se torna um "porquê" muito mais interessante. O nome vem do fato de os nós serem organizados por sua chave e uma chave do nó pai é sempre> = que seu nó filho.
Alexandre Bell
6
Eles são definitivamente independentes. No entanto, o problema de chamá-lo de "pilha" é que "a contraparte da pilha -" a pilha "- também é uma pilha real.
dan
1
Eu sei por que a estrutura de dados da pilha é chamada de pilha: porque satisfaz a propriedade da pilha. Mas por que a propriedade heap é chamada assim? Não faz sentido para mim, pois um nome como "top heavy" seria muito melhor.
Thomas Eding
31

A colisão de nomes é lamentável, mas não tão misteriosa. Heap é uma palavra pequena e comum usada para significar uma pilha, coleção, grupo etc. O uso da palavra para a estrutura de dados antecede (tenho certeza) o nome do pool de memória. De fato, a piscina teria sido uma escolha muito melhor para este último, na minha opinião. O heap conota uma estrutura vertical (como uma pilha), que se ajusta à estrutura de dados, mas não ao conjunto de memórias. Não consideramos um heap de pool de memória como hierárquico, enquanto a idéia fundamental por trás da estrutura de dados é manter o maior elemento no topo do heap (e sub-heaps).

Heap a estrutura de dados remonta a meados dos anos 60; monte o conjunto de memórias, no início dos anos 70. O termo heap (que significa pool de memória) foi usado pelo menos desde 1971 por Wijngaarden nas discussões sobre Algol.

Possivelmente, o uso mais antigo de heap como estrutura de dados foi encontrado sete anos antes, em
Williams, JWJ 1964. "Algorithm 232 - Heapsort", Communications of the ACM 7 (6): 347-348

IJ Kennedy
fonte
1
Sim, mas um monte também implica desordem e os montes de memória geralmente são desordenados. O heap da estrutura de dados é extremamente bem ordenado. Então, novamente, há uma incompatibilidade igual na outra direção, com base na definição comum de heap.
jmucchiello
É sempre apresentado como o oposto da pilha, o que deve ser suficiente para explicar o nome IMO.
Reinierpost
1
Não é coincidência - a lista livre pode ser implementada como uma fila de prioridade por meio de um heap binomial.
Heath Hunnicutt
2
@ jmucchiello: um monte de toras (veja a figura ) é bem ordenado e parece árvore. Essa é a origem do nome da estrutura de dados, de acordo com um dos meus livros de graduação.
Gioele
6

Na verdade, ler sobre a maneira como a memória é alocada (consulte Buddy Blocks ) me lembra um monte de estruturas de dados.

Travelling Tech Guy
fonte
Meu comentário sobre a resposta de Peter Zhang também é relevante aqui. O sistema binário de amigos pode ser representado como uma árvore binária e também parece um heap máximo válido quando a "chave" de cada nó é a memória total abaixo dele (mas esses valores estão implícitos e nunca mudam). Nem o algoritmo de alocação nem de liberação usa operações de heap nessa árvore binária, até onde eu sei.
Eric Dubé
5

Na IMO, é apenas um acidente / coincidência que essas duas coisas totalmente independentes tenham o mesmo nome. É como gráfico e gráfico .

MAK
fonte
Os dois gráficos podem, de alguma forma, estar relacionados. Imaginar o gráfico da função como se segue: O domínio tuplo, gama) é um vértice e um bordo conecta dois desses vértices
2
@Mit: Para gráficos contínuos, isso significaria um número infinito de vértices. Tudo bem, mas isso também torna o conceito de arestas entre os vértices sem sentido. No gráfico da função f (x) = x * 2, existe uma aresta entre (0,0) e (1,2)? Se sim, que tal (0,0) e (0,5,1)? (0,0) e (0,25,0,5)? Não há como ter o conceito de uma aresta entre os vértices; portanto, esse não é realmente um gráfico.
MAK
5

A estrutura de dados do tipo heap é usada pelo algoritmo de localização da alocação de memória disponível. O seguinte é extraído de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html .

Quando newé chamado, ele começa a procurar um bloco de memória livre que se ajuste ao tamanho da sua solicitação. Supondo que esse bloco de memória seja encontrado, ele é marcado como reservado e um ponteiro para esse local é retornado. Existem vários algoritmos para fazer isso, porque é necessário fazer um compromisso entre a varredura de toda a memória para encontrar o menor bloco livre maior que o tamanho do seu objeto ou retornar o primeiro onde a memória necessária se encaixa. Para melhorar a velocidade de obtenção de um bloco de memória, as áreas livres e reservadas da memória são mantidas em uma estrutura de dados semelhante às árvores binárias chamadas heap.

Peng Zhang
fonte
1
Sou extremamente cético quanto a isso, especificamente "... as áreas livres e reservadas da memória são mantidas em uma estrutura de dados semelhante a árvores binárias chamadas heap". Parece-me que o autor está supondo que há uma conexão, com base no nome "heap", e provavelmente está enganado. Alguém pode confirmar / refutar?
Don escotilha
1
Após algumas pesquisas leves no sistema Binary Buddy (usado no Linux), ele pode ser representado por uma árvore binária devido à forma como particiona os dados. Essa árvore binária se parece com um heap máximo válido se você observar os nós em termos de memória total, mas os nós não são inseridos nessa árvore binária como estão em um heap máximo - os nós são inseridos diretamente na menor folha de memória livre> = o tamanho solicitado. 1 2 3
Eric Dubé
1

Os termos coloquiais empilham memória e heap memory não são usados ​​no padrão C ++. O padrão usa armazenamento estático, armazenamento de threads, armazenamento automático e armazenamento dinâmico.

Mais informações podem ser encontradas na seção Duração do armazenamento do padrão.

Portanto, do ponto de vista da linguagem e da biblioteca padrão, não há confusão.

R Sahu
fonte
1

P. o que é uma pilha? R. Um heap é uma coleção de objetos colocados um em cima do outro.

Resposta à sua pergunta: O heap de memória e o binário usam o mesmo conceito que você conhece. Os dados são armazenados na forma de um heap na memória na mesma ordem em que foram gravados no programa, enquanto o heap binário é uma estrutura de dados que segue o mesmo conceito de armazenamento de dados de maneira ordenada na forma de heap (Data on top do outro). Deixe-me saber o que você pensa na seção de comentários.

Mayank Tolani
fonte
-2

Talvez o primeiro heap de memória implementado tenha sido gerenciado por uma estrutura de heap?

Adam Maras
fonte
8
Essa hipótese não parece óbvia - como um heap (a estrutura de dados) é útil para manter um heap (a região de memória dinâmica)?
9309 Keith Randall
7
-1. Eu preferiria uma declaração autorizada com evidências em vez do que é obviamente apenas um palpite.
Rob Kennedy
Altamente improvável. Parece não haver um bom motivo para usar um heap (a estrutura de dados) para gerenciar o heap (o pool de memória livre).
jason