1. Suponha que v[1 . . m] é um max-heap. Suponha que i<j e v[i]<v[j]. Se os valores de v[i] e v[j] forem trocados, v[1…m] continuará sendo um max-heap? Repita o exercício sob a hipótese v[i] > v[j].

Passo 1

O enunciado diz que temos um vetor v[1..m] que já satisfaz a propriedade de max-heap, ou seja, para todo índice k>1 vale
v\bigl[\lfloor k/2\rfloor\bigr]\ge v[k].
Escolhemos dois índices i<j e queremos saber se, ao trocar v[i] com v[j], a propriedade de heap continua válida. Vamos analisar separadamente os dois casos: (a) v[i]<v[j] e (b) v[i]>v[j].

Passo 2

Caso v[i]<v[j]. Após a troca teremos
v_{\text{novo}}[\,i\,]=v[j], \qquad v_{\text{novo}}[\,j\,]=v[i].
Devemos verificar os possíveis pontos de violação: em i e em j.
  1. Em i, compare com o pai p=\lfloor i/2\rfloor. Antes valia
    \;v[p]\ge v[i],
    mas agora exigimos
    \;v[p]\ge v[j].
    Como v[j]>v[i], pode ocorrer v[p]<v[j] e gerar violação.
  2. Em j, compare com o pai q=\lfloor j/2\rfloor. Antes valia
    \;v[q]\ge v[j],
    mas agora exigimos
    \;v[q]\ge v[i].
    Aqui não há risco de violar, pois v[q]\ge v[j]>v[i].
  3. Filhos de i e de j: no caso de i, todo filho c obedecia
    v[i]\ge v[c] e como v[j]>v[i] teremos
    v_{\text{novo}}[i]=v[j]\ge v[c],
    logo os filhos de i continuam ok. O mesmo raciocínio vale para filhos de j.
Conclusão parcial: o único possível problema é em i, comparando v[p] com o novo valor v[j]. Logo, em geral não permanece max-heap.

Passo 3

Contraexemplo para v[i]<v[j]:
Tome v=[5,\,4,\,6]. Aqui é max-heap porque 5\ge4 e 5\ge6 falha em relação a 6? Ops, corrige para
v=[5,\,6,\,4],
que é heap pois 5\ge6 falha de novo… melhor ainda:
v=[7,\,4,\,6,\,1].
Índices: i=2 v[2]=4, j=3 v[3]=6, e 4<6. Se trocarmos:
v_{\text{novo}}=[7,\,6,\,4,\,1].
Agora em i=2 o pai é p=1 com v_{\text{novo}}[1]=7\ge6 tudo bem. Mas escolhemos outro exemplo melhor para violar:
v=[5,\,4,\,6,\,1], \quad i=2,\;j=3.
Aqui é heap: 5\ge4, 5\ge6 (falha de novo!). Vamos corrigir para
v=[6,\,3,\,5,\,1], \quad i=2,\;j=3.
É max-heap pois 6\ge3 e 6\ge5. Como 3<5, trocando obtemos
v_{\text{novo}}=[6,\,5,\,3,\,1].
Ainda heap. Para violar mesmo precisamos de um pai menor que 5. Então melhor:
v=[5,\,4,\,6,\,2], \quad i=2,\;j=3.
É max-heap pois 5\ge4 e 5\ge6 falha outra vez.
Dada a dificuldade de achar um heap pequeno que violente exata- mente essa troca, fica claro pelo argumento teórico: se o pai de i tinha valor só um pouco maior que v[i], mas menor que v[j], a troca quebra v[p]\ge v_{\text{novo}}[i]. Portanto não é garantido.

Passo 4

Caso v[i]>v[j]. Após a troca teremos
v_{\text{novo}}[i]=v[j], \qquad v_{\text{novo}}[j]=v[i].
Verificações:
  1. Em i, compare com filhos c_1=2i e c_2=2i+1. Originalmente cada filho obedecia
    \;v[i]\ge v[c_k].
    Mas agora queremos
    \;v[j]\ge v[c_k].
    Como v[j]<v[i], pode ocorrer v[c_k]>v[j] e violação na relação pai-filho.
  2. Em j, compare com o pai q=\lfloor j/2\rfloor. Originalmente valia
    \;v[q]\ge v[j],
    mas agora pedimos
    \;v[q]\ge v[i].
    Como v[i]>v[j], pode dar v[q]<v[i] e violar ali também.
Conclusão: também não é garantido que continue sendo max-heap.

Passo 5

Contraexemplo para v[i]>v[j]:
Considere
v=[6,\,5,\,4,\,3].
É max-heap pois 6\ge5, 6\ge4, 5\ge3. Tome i=2 v[2]=5, j=4 v[4]=3, e 5>3. Ao trocar:
v_{\text{novo}}=[6,\,3,\,4,\,5].
Agora, em i=2, tem filho c=4 e
v_{\text{novo}}[2]=3<5=v_{\text{novo}}[4],
violando a propriedade de max-heap.

Resposta

Em nenhum dos dois casos (nem para v[i]<v[j] nem para v[i]>v[j]) a troca arbitrária de v[i] com v[j] mantém garantido que v[1..m] continue sendo um max-heap.

Exercícios relacionados