Heap sort

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (533 palavras )
  • Download(s) : 0
  • Publicado : 29 de maio de 2011
Ler documento completo
Amostra do texto
Heapsort
Possui o mesmo princípio de funcionamento da ordenação por seleção. Algoritmo:
1. Selecione o menor item do vetor. 2. Troque-o com o item da primeira posição do vetor. 3. Repita estasoperações com os n – 1 itens restantes, depois com os n – 2 itens, e assim sucessivamente.

Heapsort
Filas de Prioridades
É uma estrutura de dados onde a chave de cada item reflete a prioridade emtratar aquele item Aplicações:
SOs usam filas de prioridades, nas quais as chaves representam o tempo em que eventos devem ocorrer. Sistemas de gerência de memória usam a técnica de substituir a páginamenos utilizada na memória principal por uma nova página. Métodos numéricos iterativos são baseados na seleção repetida de um item com maior (menor) valor.
Algoritmos e Estrutura de Dados II

Ocusto para encontrar o menor (ou o maior) item entre n itens é n – 1 comparações. Isso pode ser reduzido utilizando uma fila de prioridades. Algoritmos e Estrutura de Dados II

Heapsort
Filas dePrioridades - Tipo Abstrato de Dados
Operações:
1. Constrói uma fila de prioridades a partir de um conjunto com n itens. 2. Informa qual é o maior item do conjunto. 3. Retira o item com maior chave. 4.Insere um novo item. 5. Aumenta o valor da chave do item i para um novo valor que é maior que o valor atual da chave. 6. Substitui o maior item por um novo item, a não ser que o novo item seja maior.7. Altera a prioridade de um item. 8. Remove um item qualquer. 9. Ajunta duas filas de prioridades em uma única.

Heapsort
Filas de Prioridades – Representação
Representação através de uma listalinear ordenada:
Neste caso, Constrói leva tempo O(n log n). Insere é O(n). Retira é O(1).

Representação através de uma lista linear não ordenada:
Neste caso, Constrói tem custo linear. Insere éO(1). Retira é O(n). Algoritmos e Estrutura de Dados II

Algoritmos e Estrutura de Dados II

Heapsort
Filas de Prioridades – Representação
A melhor representação é através de uma estruturas de...
tracking img