Ciencia da computação

ORDENAÇÃO: ALGORITMO HEAPSORT
Leandro R. M. Xavier (UNICENTRO), Leonildo M. Azevedo (UNICENTRO), e-mail: [e-mail].
Universidade Estadual do Centro-Oeste, Setor de Ciências Exatas, Departamento de Computação, Guarapuava PR.
Palavras-chave: heap, heapsort, ordenação.
Resumo
Este trabalho visa apresentar de forma clara e objetiva o funcionamento do algoritmo heapsort expondo suas vantagens e desvantagens. O algoritmo rearranja um vetor em ordem crescente de forma relativamente rápida e eficiente (FEOFILOFF, 2009). O segredo do algoritmo é uma estrutura de dados chamada de heap, que consiste em uma arvore cuja raiz é o elemento de menor valor, caso seja um heap de mínimo, ou o de maior valor, caso seja um heap de máximo (RUIZ, 2007).
Introdução
Um vetor ordenado em ordem crescente é o primeiro passo para a solução de diversos problemas práticos. Existem enumeras maneiras de se ordenar um vetor: algumas elementares, outras mais elaboradas e eficientes. Todas as técnicas consistem em rearranjar (ou seja, permutar) os elementos de um vetor de tal modo que ele se torne crescente (FEOFILOFF, 2009). Dentre os algoritmos elementares encontra-se o algoritmo de inserção e algoritmo de seleção. Já um pouco mais sofisticado e rápido existe o algoritmo Mergesort porem utiliza vetor auxiliar para ser mais eficiente, o algoritmo heapsort (abordado neste trabalho) é sofisticado, rápido e não necessita de vetor auxiliara para realizar a ordenação dos elementos do vetor (FEOFILOFF, 2009). Além dos algoritmos citados ainda existem vários outros métodos de ordenação, está sempre foi uma área atrativa para os pesquisadores de ciência da computação (RUIZ, 2007).
Resultados e Discussões
Heapsort
É um método de ordenação conhecido por utilizar o modelo de arvores no método de seleção direta, ele utiliza a estrutura de dados heap, que consiste em uma árvore binária cujo raiz é o elemento mínimo ou máximo dependendo do tipo de heap a ser utilizado. Um heap