Heap Implementação HeapSort Exercícios
Estruturas de Dados II
Heap
Prof. Leonardo C. R. Soares - [Link]@[Link]
Instituto Federal do Sudeste de Minas Gerais
30 de abril de 2025
1/35
Heap Implementação HeapSort Exercícios
Pensando um pouco
Você precisa representar a árvore binária abaixo em um vetor. Como
você faria? Qual seria a regra para determinar quem é o antecedente
direto de um determinado nó?
2/35
Heap Implementação HeapSort Exercícios
Heap
Definição
Heap é uma árvore binária que atende a duas propriedades básicas:
▶ O valor de um nó deve ser maior (ou menor) ou igual ao valor
de seus filhos;
▶ A árvore binária deve ser completa ou quase-completa da es-
querda para a direita.
3/35
Heap Implementação HeapSort Exercícios
Heap
Definição
Heap é uma árvore binária que atende a duas propriedades básicas:
▶ O valor de um nó deve ser maior (ou menor) ou igual ao valor
de seus filhos;
▶ A árvore binária deve ser completa ou quase-completa da es-
querda para a direita.
Caso o valor de um nó seja maior ou igual aos valor de seus filhos,
temos um heap máximo. Caso o valor seja menor ou igual aos dos
filhos, temos um heap mínimo.
3/35
Heap Implementação HeapSort Exercícios
Heap Máximo
4/35
Heap Implementação HeapSort Exercícios
Heap Máximo
5/35
Heap Implementação HeapSort Exercícios
Heap
Dada as propriedades de um Heap, sua altura é Θ(log n), visto ser
composto por uma árvore binária quase-completa. Essa característica
permite que as operações de inserção e remoção sejam eficientes.
6/35
Heap Implementação HeapSort Exercícios
Implementação
Utilizaremos um vetor para implementar o Heap. A raiz estará na
posição zero do vetor. O filho da esquerda de um nó no índice i
estará sempre na posição 2 ∗ i + 1. O filho da direita de um nó no
índice i estará sempre na posição 2 ∗ i + 2. O pai de um nó no índice
i estará sempre na posição ⌊(i − 1)/2⌋.
7/35
Heap Implementação HeapSort Exercícios
Heap
heap=[88, 87, 73, 47, 54, 6, 0, 43]
8/35
Heap Implementação HeapSort Exercícios
Heap
Inserção
A adição de um novo elemento no heap é sempre feita na próxima
posição livre do vetor. Após a inclusão, deve-se mover o nó inserido
de modo que a primeira propriedade do heap (o valor de um nó deve
ser maior ou igual ao valor de seus filhos) continue verdadeira.
9/35
Heap Implementação HeapSort Exercícios
Inserção
Considere que iremos inserir um nó com valor 100 no heap abaixo.
10/35
Heap Implementação HeapSort Exercícios
Inserção
A inserção é feita mantendo a árvore quase-completa.
11/35
Heap Implementação HeapSort Exercícios
Inserção
Como o nó inserido é maior que seu pai, trocamos os nós de lugar
para garantir a primeira propriedade do heap.
12/35
Heap Implementação HeapSort Exercícios
Inserção
Repetimos o passo anterior enquanto for necessário.
13/35
Heap Implementação HeapSort Exercícios
Inserção
A inserção de um elemento no heap é O(log n)
14/35
Heap Implementação HeapSort Exercícios
Heap
Remoção
A remoção de um elemento do heap é sempre feita na raiz. Para
manter a propriedade de ser uma árvore quase-completa, troca-se o
valor da raiz com a última folha e remove-se a folha. Depois disso,
devemos corrigir a posição dos elementos do vetor para garantir que
a primeira propriedade heap volte a ser verdadeira. Este processo
denomina-se heapify.
15/35
Heap Implementação HeapSort Exercícios
Remoção
Usaremos o heap abaixo para ilustrar o processo de remoção de um
nó.
16/35
Heap Implementação HeapSort Exercícios
Remoção
Primeiro trocamos a raiz com a última folha.
17/35
Heap Implementação HeapSort Exercícios
Remoção
Remove-se a última folha.
18/35
Heap Implementação HeapSort Exercícios
Remoção
O processo de heapify é aplicado à raiz para garantir a primeira
propriedade do heap. A raiz é trocada pelo maior de seus filhos. O
processo se repete recursivamente até que o heap esteja correto.
19/35
Heap Implementação HeapSort Exercícios
Remoção
A remoção de um elemento no heap é O(log n)
20/35
Heap Implementação HeapSort Exercícios
Dúvidas?
21/35
Heap Implementação HeapSort Exercícios
Dúvidas?
Mais alguém?
21/35
Heap Implementação HeapSort Exercícios
Dúvidas?
Mais alguém? Não?
21/35
Heap Implementação HeapSort Exercícios
Dúvidas?
Mais alguém? Não? Então ótimo. Implemente o método de inserção
e remoção!
21/35
Heap Implementação HeapSort Exercícios
Heap
22/35
Heap Implementação HeapSort Exercícios
Heap
23/35
Heap Implementação HeapSort Exercícios
Heap
24/35
Heap Implementação HeapSort Exercícios
Heap
25/35
Heap Implementação HeapSort Exercícios
Heap
26/35
Heap Implementação HeapSort Exercícios
Heap
27/35
Heap Implementação HeapSort Exercícios
Heap
28/35
Heap Implementação HeapSort Exercícios
Heap
29/35
Heap Implementação HeapSort Exercícios
HeapSort
Definição
Utilizando-se a estrutura de dados heap é possível implementar um
algoritmo eficiente de ordenação O(n log n). O algoritmo é extre-
mamente simples:
1. Construa o heap à partir do vetor original;
2. Troque a raiz com a última folha;
3. Diminua o tamanho do heap em uma unidade;
4. Reconstrua o heap com o método heapfy;
5. Repita os passos 2 a 4 até o heap ter tamanho 1.
30/35
Heap Implementação HeapSort Exercícios
HeapSort
31/35
Heap Implementação HeapSort Exercícios
HeapSort
32/35
Heap Implementação HeapSort Exercícios
HeapSort
33/35
Heap Implementação HeapSort Exercícios
Exercícios
1. Implemente os exemplos apresentados.
2. Implemente um Heap Mínimo.
3. Como ficariam as fórmulas para definir os filhos de um heap
cujo índice inicial do vetor fosse 1?
4. Em qual nível pode estar o segundo maior elemento de um heap
máximo?
5. Escreva um método que verifique se um determinado vetor é
um heap máximo.
6. Implemente todos os métodos eficientes de ordenação apresen-
tados (desconsidere o método de ordenação por contagem).
Gere um vetor de números inteiros suficientemente grande para
que o processo de ordenação não seja trivial. Execute cada um
dos métodos (para a mesma entrada) e compare os resultados.
Repita o experimento pelo menos 10 vezes. Algum método do-
minou o experimento?
34/35
Heap Implementação HeapSort Exercícios
35/35
