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.