Árvores binárias: a pilha.

David Pynes Blocked Desbloquear Seguir Seguindo 12 de janeiro

Como reter valores máximos.

Introdução

Em 1964, J. Williams, o canadense de origem galesa, desenvolveu uma estrutura para encontrar valores máximos. Essa estrutura é o heap. O heap é semi-ordenado, com o valor máximo sempre no topo.

Por quê

Digamos que você esteja no comando de um hospital e haja vários pacientes na sala de espera. Enquanto cada paciente espera pelo médico, os pacientes formam uma fila . Agora imagine que um paciente é levado para o hospital em estado de emergência. Este paciente deve ser colocado no final da fila com os outros pacientes ou deve ser dada prioridade ao paciente?

Na computação, esse conceito de prioridade é semelhante. O heap dá prioridade por ter valores mais altos acima do heap.

o que

O heap é uma árvore binária com duas propriedades adicionais.

  1. O heap está completo. Isso significa que todos os ramos da árvore têm os dois filhos (exceto o último nível).
  2. O heap é semi-ordenado. Isso significa que os nós de nível superior são sempre maiores que os de nível inferior, o que também implica o nó superior é o máximo.

Os heaps são completos, então os heaps são frequentemente implementados dentro de uma estrutura de dados contígua, isto é, um array .

Vamos descrever a conexão entre o array e a árvore binária.

Observe na imagem acima que o primeiro índice (da matriz) é a raiz (da árvore binária).

Agora observe as setas da matriz imitar as setas da árvore binária.

A conexão aqui é que um pai e um filho em uma árvore binária podem ser calculados em uma matriz como índice i*2+1 (esquerda) e i*2+2 (direita).

Isso também significa que o pai de uma criança pode ser calculado no floor(i-1/2) .