- Suponha que
é um max-heap. Suponha que
e
. Se os valores de
e
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
que já satisfaz a propriedade de max-heap, ou seja, para todo índice
vale
Escolhemos dois índices
e queremos saber se, ao trocar
com
, a propriedade de heap continua válida. Vamos analisar separadamente os dois casos: (a)
e (b)
.
Passo 2
Caso
. Após a troca teremos
Devemos verificar os possíveis pontos de violação: em
e em
.
- Em
, compare com o pai . Antes valia
,
mas agora exigimos
.
Como, pode ocorrer e gerar violação. - Em
, compare com o pai . Antes valia
,
mas agora exigimos
.
Aqui não há risco de violar, pois. - Filhos de
e de : no caso de , todo filho obedecia
e como teremos
,
logo os filhos decontinuam ok. O mesmo raciocínio vale para filhos de .
Conclusão parcial: o único possível problema é em
, comparando
com o novo valor
. Logo, em geral não permanece max-heap.
Passo 3
Contraexemplo para
:
Tome . Aqui é max-heap porque
e
falha em relação a
? Ops, corrige para
Tome
que é heap pois
falha de novo… melhor ainda:
Índices:
,
, e
. Se trocarmos:
Agora em
o pai é
com
tudo bem. Mas escolhemos outro exemplo melhor para violar:
Aqui é heap:
,
(falha de novo!). Vamos corrigir para
É max-heap pois
e
. Como
, trocando obtemos
Ainda heap. Para violar mesmo precisamos de um pai menor que
. Então melhor:
É max-heap pois
e
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 tinha valor só um pouco maior que
, mas menor que
, a troca quebra
. Portanto não é garantido.
Dada a dificuldade de achar um heap pequeno que violente exata- mente essa troca, fica claro pelo argumento teórico: se o pai de
Passo 4
Caso
. Após a troca teremos
Verificações:
- Em
, compare com filhos e . Originalmente cada filho obedecia
.
Mas agora queremos
.
Como, pode ocorrer e violação na relação pai-filho. - Em
, compare com o pai . Originalmente valia
,
mas agora pedimos
.
Como, pode dar e violar ali também.
Conclusão: também não é garantido que continue sendo max-heap.
Passo 5
Contraexemplo para
:
Considere
Considere
É max-heap pois
,
,
. Tome
,
, e
. Ao trocar:
Agora, em
, tem filho
e
violando a propriedade de max-heap.
Resposta
Em nenhum dos dois casos (nem para
nem para
) a troca arbitrária de
com
mantém garantido que
continue sendo um max-heap.