Heap Sort

Prévia do material em texto

Universidade Federal de Uberlândia (UFU) 
 
Sistemas de Informação 
 
 
 
 
Heap 
 
 
 
 
 Orientador: Daniel Duarte Abdala 
 
 
 
Adelson Pacheco dos Reis 
Lucas Rodrigues da Cunha 
Valdomiro Caetano Martins 
 
 
 
 
 
 
 
 
 
 
Monte Carmelo 
2013 
2 
RESUMO 
 
 
 
Este trabalho tem o objetivo de mostrar e descrever o funcionamento da estrutura de 
dados Heap, na qual é implementada em um vetor como árvore binária. 
 
Palavras-chave: heap, dado, numero. 
3 
INTRODUÇÃO 
 
Uma Heap é uma estrutura de dados implementada como árvore binária seguindo 
ordens de prioridade. Em uma “Max Heap” todos os filhos devem ser menores que 
seus respectivos pais. Já no caso de uma “Min Heap” todos os filhos devem ser 
maiores que seus pais. 
O elemento Raiz é armazenado na primeira posição do vetor, o filho á esquerda 
segue a regra de posicionamento (2*índice)+1 e o filho á direita (2*índice)+2, onde 
índice é a posição do pai. Esta regra vale para todos os demais nós filhos. 
As principais aplicações da Estrutura Heap são na implementação de Filas de 
prioridade e em alguns algoritmos como o algoritmo de ordenação HeapSort e 
algoritmos como o de Djikstra. 
Observação: 
A estrutura de dados Heap não é a mesma coisa que a heap que é referenciada 
como a região de memória utilizada para alocação dinâmica. 
 
 
 
 
 
A estrutura utilizada foi do tipo struct “Heap”, com uma entrada de dados do tipo Int 
que receberá o número a ser inserido. A estrutura foi colocada na forma de array, já 
que a Heap permite que sua estruturação seja feita de forma estática. 
As opções presentes no algoritmo são: 
• Inserção; 
• Remoção do maior valor; 
• Exibição da Heap. 
 
 
4 
1 FUNÇÃO DE INSERÇÃO 
 
 
 
Na função de inserção é passado o vetor do tipo Struct e um contador por referência. 
Este contador é utilizado para controle de quantidade de elementos adicionados na 
heap. Logo após o recebimento do elemento, ele é passado na função 
verifica_inseridos para verificar se já existe o mesmo elemento cadastrado na Heap. 
Caso haja, ele não será inserido na Heap. 
5 
2 FUNÇÃO TROCA 
Função responsável por verificar se existe algum no filho maior que o pai. Se existir, 
ela inverte o pai com o filho. 
 
 
 
A função troca funciona da seguinte maneira: 
Toda vez que um número é armazenado na Heap, essa função é chamada para 
colocá-lo no seu devido lugar, de acordo com a lógica apresentada: Todo filho deve 
ser menor que o pai. 
Para saber se um número é maior que seu pai e, eventualmente, ordenar toda a 
Heap, foi preciso fazer um laço para percorrê-la. Além disso, foi necessário duas 
estruturas de validação (para conferir se a posição do número é impar ou par). Em 
ambas as estruturas, é verificado se o filho é maior que o pai. 
 
6 
3 FUNÇÃO DE VERIFICAÇÃO DE ELEMENTOS INSERIDO 
 
 
A função verifica_inseridos recebe como argumentos: 
• A Heap; 
• O “cont” contendo a quantidade de elementos da Heap; 
• Um string “dado” com o dado a ser inserido na Heap; 
• A variável “num”, que é passada por referencia. 
Logo a string “dado” e a variável “num” são passadas para a função eh_numero que 
faz a verificação se o dado é um numero. Caso seja inválido, a mensagem de 
caractere inválido será exibida, senão será executado o laço que irá percorrer toda a 
Heap testando se já existe o mesmo número inserido. Se existir será retornado o 
valor 0, caso contrário é retornado 1. 
 
7 
4 FUNÇÃO DE REMOÇÃO DO MAIOR VALOR 
 
 
A função de remoção recebe a Heap e o “cont” passado por referência - para saber 
a quantidade de elementos da Heap e caso a exclusão seja feita, o “cont” precisar 
ser alterado -. Para remoção em uma estrutura de Dados Heap, seguimos a regra de 
remover apenas a raiz. 
Em primeiro caso verifica-se se a Heap está vazia. Caso esteja, é mostrada a 
mensagem de Heap vazia, caso contrário a raiz será removida e cada elemento é 
movimentado para a posição anterior da que se encontrava. Em seguida, o contador 
é decrementado e a Heap é envida para a função troca pra verificar se existe algum 
nó no lugar errado e reorganizá-la. 
 
8 
5 FUNÇÃO DE EXIBIÇÃO 
 
 
A função de exibição é recebida a Heap e seu tamanho, representado pela variável 
“cont”. Primeiro é verificada se a Heap está vazia. Caso esteja a mensagem de Heap 
vazia é mostrada, senão o laço será executado enquanto o contador do laço for 
menor que a quantidade de elementos da Heap e cada elemento contido na Heap 
será mostrado. 
9 
6 FUNÇÃO DE VALIDAR O ELEMENTO INSERIDO 
 
 
 
Função usada para aceitar apenas números. Ela recebe um char com o dado e o 
transforma em int, passando por várias verificações e restrições. 
Primeiramente é analisado se o primeiro caractere é um “–“. Se for, a variável “tam” 
é inicialmente incrementada (isto acontece pois é a variável “tam” que determina se 
todos os caracteres da string foram transformados em inteiros). Caso contrário, “tam” 
não é incrementada, pois logicamente o número é positivo. 
Em ambas as condições, um laço percorre toda a string verificando se cada 
caractere corresponde a um inteiro da tabela Ascii. Caso seja, a variável “num” 
recebe o seu próprio valor somado com o dado multiplicado por sua ordem. 
10 
Logo depois é verificado se os todos os caracteres foram transformados em inteiro. 
Se a condição for satisfeita, a variável “numero” – passada por parâmetro – recebe 
seu devido valor e a função retorna sucesso. Caso a condição não é satisfeita, a 
função falha.