Qual é a diferença entre Heap e Stack?

Pergunta originalmente respondida no QUORA em 03/07/2019

Definição de Heap:

Heap é uma árvore binária com chaves em seus nós (uma chave por nó) conforme a seguir:

Ela é essencialmente completa, ou seja, todos os seus níveis são completos menos o último nível, onde somente a chave mais à direita pode eventualmente estar faltando.

*A chave de cada nó pai (acima) é maior ou igual à chave filho (que vem abaixo).

Observe: Os elementos de uma heap são ordenados de cima para baixo (junto com qualquer caminho abaixo de sua raiz), porém eles não são ordenados da esquerda para a direita.

Algumas propriedades de uma heap:

  • Dado n, há uma única árvore binária com n nós que é essencialmente completa com h=[log2n]
  • .
  • A raiz contém o maior valor chave
  • Uma sub árvore extraída de qualquer nó de uma heap também é uma heap
  • Uma heap pode ser representada como um array.

Fonte da definição de uma heap: https://cs.winona.edu/lin/cs440/…


Definição de Stack:

Stack ou pilha é um conjunto ordenado de itens no qual novos itens podem ser inseridos e a partir do qual podem ser eliminados itens um uma extremidade chamada topo da pilha.

Ao contrário do vetor, a definição de pilha abrange a inserção e remoção de itens o que a faz um objeto dinâmico, mutável.

Por definição somente uma extremidade é designada como topo da pilha. Novos itens podem ser adicionados no topo da pilha, consequentemente deslocando o topo da pilha para cima e os itens que estão no topo da pilha podem ser removidos, consequentemente deslocando o topo da pilha para baixo.

O topo da pilha é a extremidade em que os dados são inseridos e retirados da pilha e por essa razão uma pilha também é chamada de LIFO, last in first out, último a entrar, primeiro a sair.

A pilha, computacionalmente, sempre é vista pelo topo, de cima para baixo (somente pode-se observar o topo da pilha), embora para explicar seu funcionamento a pilha seja exibida em perfil.

Para acessar o último elemento de uma pilha é necessário desempilhar os elementos que estiverem por cima do último elemento para poder acessá-lo, conforme imagem abaixo (clique para ampliar).

Fonte da difinição de stack: TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGESNSTEIN, Moshe J.. Estruturas de Dados Usando C. São Paulo: Pearson, 2013. 884 p. ISBN 13: 978-85-346-0348-5.

Last updated by at .