Heap Sort

Páginas: 3 (722 palavras) Publicado: 4 de junho de 2014
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çãobaseado 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 oserviç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é pelomenos 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 serrepresentada 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 elementossã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 formaque 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 econstante. 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 paradireita. 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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Heap sort
  • Heap sort
  • Merge Sort, Quick Sort e Heap Sort
  • Heap
  • sort
  • sort
  • Quick sort e shell sort
  • selection sort

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!