Um heap é uma estrutura de dados em forma de árvore que respeita a chamada “propriedade de heap”:
🗼
Se P é o nó-pai de C, então o valor de P é maior ou igual (em um max-heap) ou menor ou igual (em um min-heap) ao valor de C.
Um exemplo de um max-heap com 8 nós
Existem dois tipos principais de heaps:
Max Heap: O valor do nó-pai deve ser maior ou igual ao de seus nós-filho.
Min Heap: O valor do nó-pai deve ser menor ou igual ao de seus nós-filho.
Vamos nos concentrar em max-heap, já que a maioria das bibliotecas padrão implementa um max-heap para filas de prioridade (priority queues). Em um max-heap, a raiz da árvore é o maior elemento, enquanto as folhas são as menores. No entanto, não há uma ordenação específica para os nós-folha. Assim, a única garantia é de que o nó-raiz é o maior e que seus nós-filho são menores ou iguais ao seu valor.
Note que a última linha do heap é sempre preenchida da esquerda para a direita. Portanto, a folha mais à esquerda é preenchida primeiro e a folha mais à direita é preenchida por último – como mostrado na figura acima.
Implementação
Um heap pode ser implementado como um array, em que o primeiro elemento do array representa o nó-raiz. Como cada nó tem apenas 2 nós-filho, podemos organizar a indexação da seguinte forma:
O elemento raiz tem índice 1.
Os filhos esquerdo e direito estão localizados em 2i e 2i+1, respectivamente, para todos os nós.
O nó-pai de um elemento no índice i está no índice i // 2.
O heap acima pode ser representado em uma lista como:
# Basta ler cada linha na imagem e escrever os números na mesma ordem
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Ou para visualizar melhor
heap = [None, # Ignoramos o índice [0] para termos uma indexação mais simples
8, # Índice [1]
5, 7, # Índices [2, 3]
1, 1, 6, 3, # Índices [4, 5, 6, 7]
1] # Índice [8]
Desafio: Verificar se a árvore binária é um heap
Dada uma árvore binária representada por um array de n números (com a indexação descrita acima), você deve verificar se ela satisfaz as propriedades de um max-heap.
Entrada
A primeira linha da entrada contém um único inteiro n (1 ≤ n ≤ 100 000).
A linha seguinte contém n inteiros separados por espaço () que representam os valores dos elementos no heap.
Saída
O programa deve imprimir Yes caso a árvore binária de entrada satisfaça a propriedade de max-heap. Caso contrário, deve imprimir No.
Exemplos
Entrada
Saída
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explicação
Exemplo 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Exemplo 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
