Introdução a java

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 todos filhos 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: 16 14 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 do