Heapsort

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1157 palavras )
  • Download(s) : 0
  • Publicado : 19 de abril de 2013
Ler documento completo
Amostra do texto
FATEC DE PRAIA GRANDE
ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

ESTRUTURA DE DADOS

HEAPSORT

ITAY JESUS DE SENA FILHO
JAQUELINI APARECIDA DOS SANTOS LIMA
MARCELA MORAIS
WELLINGTON ALVES ROSENDO

PRAIA GRANDE
MARÇO/2013
1. INTRODUÇÃO
Os algoritmos de ordenação ou classificação constituem uma classe de algoritmos extremamente estudada e muito popular. Em diversas aplicações asordenações de uma das etapas, dentre muitas outras a serem efetuadas, de modo que selecionar o melhor algoritmo de ordenação é extremamente importante nestes casos.
Em busca de índices previamente ordenados, por exemplo, é a maneira mais eficiente de busca por um elemento qualquer de uma coleção.
O HeapSort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenaçãopor seleção. Foi desenvolvido em 1964 por Robert W. Floyd e J.W.J. Williams.
2. METODOLOGIA
Para ordenar, o HeapSort usa um Heap.
Heap é uma árvore binária com as seguintes propriedades:
* O valor de cada nó não é menor que os valores armazenados em cada filho;
* A árvore é perfeitamente balanceada e as folhas no último nível estão todas nas posições mais a esquerda.

3.1FUNCIONAMENTO
• Transformação do vetor em um heap binário:

• Estrutura do heap completa:

3.2 ORDENAÇÃO

• A cada iteração seleciona-se o maior elemento (na raiz do heap) e o adiciona no início de um segmento ordenado:

• E assim sucessivamente:

• Após a cada seleção de elemento, o heap deve ser reorganizado para continuar sendo um heap binário máximo:

• A cada iteração selecionao maior elemento do heap (sempre está na primeira posição) e o troca com o elemento no final do segmento não-ordenado:

• Após a troca, o novo elemento raiz do heap deve ser ajustado (deve-se chamar ajustaElemento para o nodo raiz):

• O processo termina quando o heap tiver somente 1 elemento (vetor ordenado):
Vetor ordenado : 1, 2, 3, 4, 5, 7, 8, 9, 11

3. APLICAÇÃO
Uma sequênciapreviamente ordenada tem aplicação prática na resolução dos seguintes problemas: busca, par mais próximo (dado uma sequência de números), unicidade de elementos, distribuição de frequência, convex hull, etc.
4. IMPLEMENTAÇÃO
Código desenvolvido na linguagem JAVA:
import javax.swing.JOptionPane;
import java.lang.System;
public class Heap {
public static void main(String[] args) {int t;
t = Integer.parseInt(JOptionPane.showInputDialog("Digite o tamanho do vetor:"));
int[] vet = new int[t];
for(int i = 0; i < t;i++){
vet[i] = Integer.parseInt(JOptionPane.showInputDialog("Digite um numero do vetor:"));
}
System.out.println("O vetor atual é:");
for(int i = 0; i < t;i++){
System.out.print(vet[i]+ " ,"); // mostra na tela o vetor atual desordenado
}
Teste c = new Teste();
c.heapSort(vet);
}
}
public class Teste {
//recebe o vetor que será ordenado
public static void heapSort(int[] v)
{
divide(v);
int n = v.length;// atribui a n o tamanho do vetor
for (int i = v.length - 1; i > 0; i--)
{trocar(v, i , 0);//troca o valor do primeiro indice com o segundo
//diminuo o valor de n para que seja apenas verificados os numeros restantes
maxHeap(v, 0, --n);
}
System.out.println("VETOR ORDENADO");
for (int i = 0; i < v.length;i++){//exibe o vetor já ordenado
System.out.print(v[i] + ", ");
}}
//saber em qual índice esta o pai do ultimo nodo
private static void divide(int[] v)
{
//divide o vetor para saber qual pai vai ser comparado
for (int i = v.length/2 - 1; i >= 0; i--)
maxHeap(v, i , v. length );
}
//verifica qual é o maior numero do nodo
private static void maxHeap(int[] v, int pai, int...
tracking img