Lista de exercicio 6 Analise e Projeto de Algoritmos

Aluno: Vinicius Barcelos Silva
Matricula: 108251
Lista 6 6.1­1
O máximo de vértices de uma heap com altura h vai ser de (2^h+1)­1 e o numero minimo será de 2^h vertices. 6.1­4
Assumindo que todos os elementos da heap máxima são distintos, o menor elemento estara sempre em uma folha. 6.1­5
Sim, em arranjo que é classificado em ordem crescente é um heap minimo. 6.1­6
Não, a sequência (23, 17, 14,6, 13, 10, 1, 5, 7, 12) não é um heap máximo. 6.1­7
Levando em consideração o filho a esquerda do nó na posição ⌊ n / 2 ⌋ + 1. ESQUERDA ( ⌊ n / 2 ⌋ + 1 ) = 2 ( ⌊ n / 2 ⌋ + 1 ) > 2 ( n / 2 ­ 1 ) + 2 = n ­ 2 + 2 = n Uma vez que o índice do filho a esquerda é maior do que o numero de elementos no heap, o nó não tem filhos, portanto é um nó folha. O mesmo vale para nós com índices maiores. 6.2­2
Min­Heapify(i,A[]){
l = (i << 1) + 1 ; r = (i << 1) + 2 ; smallest = i ; if(l < heap­size(A) && A[l] < A[i]) smallest = l ; if(r < heap­size(A) && A[r] < A[smallest]) smallest = r ; if(smallest != i) swap(A[i],A[smallest]) ;
Min­Heapify(smallest,A) ;
}

6.2­3
Nada é feito quando se chama MAX­HEAPIFY(A, i) quando o elemento A[i] é maior que seus filhos

6.2­4

Não terá efeito, pois nesse caso esse nó é uma folha. A comparação no heap não resultará em nada pois os elementos estão acima dele são maiores. 6.2­5
Iterative Max­Heapify(i,A[]){ while(1) l = (i << 1) + 1 ; r = (i << 1) + 2 ; largest = i ; if(l < heap­size(A) && A[l] > A[i]) largest = l ; if(r < heap­size(A) && A[r] > A[largest]) largest = r ; if(largest != i) swap(A[i],A[largest]) ; i = largest ; else break ;
}

6.3­1

6.4­2
Inicialização: O subarrayA [ i + 1 ... n ] está vazio, assim, a invariante detém. Manutenção: A[ 1 ] é o maior elemento em A[ 1 ... i ] e é menor do que os elementos em A[ i + 1 ... n ].
Quando vamos colocar o elemento na posição i, A[ i ... n ]contém os maiores elementos ordenados. Diminui o tamanho do heap e chama