Heap Sort

HeapSort

Síntese

Este artigo tem como objetivo apresentar o algoritmo de ordenação HeapSort e suas principais características.

1. Introdução

O heapsort é um algoritmo de ordenação baseado na estrutura de dados Heap. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J. Williams. Trata-se de um vetor que trabalha como uma árvore binária completa. Portanto o algoritmo consegue fazer o serviço sem usar um vetor auxiliar, efetuando somente trocas entre os elementos e tornando-se uma representação compacta. Basicamente o algoritmo realiza a ordenação simulando uma fila de prioridades, onde a raiz da arvore será o elemento prioritário.

2. Características

Um heap é uma estrutura de dados organizada como uma árvore binária balanceada, que deve estar sempre completa até pelo menos seu penúltimo nível. Deve ser organizada de tal forma que todos os nós sejam menores que seus pais (ou que todos os nós sejam maiores que seus pais). É implementada na forma de um vetor, e pode ser representada desta forma ou como uma árvore.
O heapsort é um algoritmo de dois passos: o primeiro passo utiliza um heap para inserção dos elementos de forma ordenada. No segundo passo, os elementos são retirados da heap de forma que a cada elemento retirado a heap seja reconstruída, para garantir a ordenação. Para controle do heap e do array ordenado, o algoritmo pode ser implementado de forma que os dois sejam controlados no mesmo array, ou com dois arrays separados.
É um algoritmo in-place, ou seja, transforma os elementos recebidos com um espaço extra de armazenamento pequeno e constante. Porém não é um algoritmo estável, ou seja, não preserva a ordem de registros de chaves iguais.

3. Funcionamento

A inserção em uma heap funciona no sentido folha para raízes, esquerda para direita. Assim o primeiro elemento do conjunto que se pretende ordenar (A) é adicionado como raiz, e o segundo elemento (B) é adicionado como filho à esquerda do elemento A. Um terceiro elemento C seria