Introdução a java

Páginas: 6 (1321 palavras) Publicado: 23 de outubro de 2011
2.2 Heaps
2.2.1. Conceito
2.2.2 Manutenção
2.2.3 Criação
2.2.4 O algoritmo Heapsort

Heaps

Este nova estrutura fornecerá um método rápido e simples de ordenação.

Conceito

Definição 1: Árvore Binária
É uma árvore vazia ou uma árvore na qual qualquer nó possui, ou um filho direito, ou um esquerdo, ou ambos.
A árvore binária será dita completa quando todosfilhos do nível mais alto possuírem filho esquerdo e filho direito. Isto é cada nó tem zero ou 2 filhos.

Exemplos de árvores binárias e não binárias, completas e não completas

FIGURAS no quadro

Número de nós numa árvore binária completa

nível 0 : 1 nó
1 : 2 nós
2 : 4 nós
3 : 8 nós
4 : 16 nós
(
i : 2i nós

Número total de nós em função da altura h é:

Definição 2 :Árvore Heap
Heap é uma árvore binária completa ou uma árvore binária na qual
• se eliminarmos as folhas do nível mais alto, ela se torna completa
• as folhas do nível mais alto estão mais à esquerda possível

Exemplos:

FIGURAS no quadro

Contra Ex.

Figuras no quadro.

Representação de Heaps

Considere a seguinte árvore:

Esta árvore pode ser armazenada num array.Como temos 10 elementos na árvore, o array terá 10 elementos. A raiz é armazenada na primeira posição do vetor ou array. A seguir teremos seu filho esquerdo, na posição um e o filho direito na posição dois. A seguir virão os filhos esquerdo e direito respectivamente do primeiro e segundo filho. Continuamos a armazenar desta maneira.
No exemplo teremos:

Posição: 1 2 3 4 5 6 7 8 9 10
Valor: 1614 10 8 7 9 3 2 4 1

Um vetor que representa um heap tem as seguintes propriedades:

HeapSize(A): número de elementos no heap armazenados no vetor;
Length(A): número de elementos no vetor;
A[1..length(A)] pode conter números válidos
HeapSize(A) ( Legth(A);
A raiz da árvore é A[1].

As funções Pai, Esq e Direção representam respectivamente, o índice do nó Pai de cada nó; o índice dofilho esquerdo e direito de cada nó. As funções são facilmente implementadas:

Pai (i)
return (i/2 (

Esq(i)
return 2i

Dir(i)
return 2i +1

Exemplos na figura acima:
Pai(3) é (3/2 ( = 1 , ou seja Pai(3) é a raiz.
Pai(8) é (8/2 ( = 4 , ou seja Pai(8) está na posição 4 e tem o valor de 8
Esq(4) é 2 x 4 = 8, ou seja, o filho esquerdo de quem está posição 4 éEsq(4) e está na posição 8 e tem o valor de 2.
Dir(2)= 2 x 1+1=5, ou seja ofilho direito do elemento da posição 2 está na posição 5 que tem o valor 7.

Definição 3 : Fila de Prioridades

É um heap em que a chave de um nó é sempre menor ou igual às chaves de seus eventuais filhos. ( dualmente * ou ( *)
A[Pai(i)] ( A[i]
Na representação usad anteriormente.

Exemplo :A[Pai(i)] ( A[i] é valido para todo nó i.

Contra Exemplo:

A[Pai(i)] (A[i] é Falso para i = 6, que vale 20 e seu pai vale 15.

A[Pai(6)] = A[3] = 15

15(20 é Falso.

Mantendo a Propriedade do Heap

- Assume-se que as árvores binárias Esq(i) e Dir(i) são heaps mas A[i] é menor o valor de seus filhos
Exemplo:

A = .

Para i=2 não temos a propriedade do heap, pois 4 < 14, que éseu filho esquerdo. Para corrigir a situação trocamos os valores dos filhos, sucessivamente até que tenhamos a propriedade re-estabelecida.

Como para i=2 a propriedade não vale, trocamos o seu valor pelo valor do filho que causa o problema, que é o filho esquerdo que está na posição 4.

Agora, o elemento da posição i=4 é que quebra a propriedade. No caso, o elemento que causa o problemaé o filho direito. Vamos trocá-lo novamente:

Agora A[i] é representa um heap.

A=

N= comprimento [A]

Heapsize = no. de elementos no heap

O algoritmo seguinte mantém a propriedade do heap, a partir do elemento de posição i.

Heapify (A,i)

1. e(Esq(i) // maior (i
2. d(Dir(i)
3. se e A(i)
4. então maior (e
5. senão maior (i
6. se d A[maior]
7....
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Introdução ao Java
  • Introdução ao Java
  • Introdução ao Java ME
  • Introdução a Java
  • Introdução a Java
  • Trabalho de introdução a java
  • Introdução a java script a
  • Introdução à Linguagem de Programação Java

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!