MAC122 - Lista 4 - Heapsort

1. Simule a execução do heapsort no vetor abaixo:

         13    1    4    19    20    12    11    7    8    2    17 
         

   Indique na sua simulação as comparações que estão sendo feitas e o resultado de cada chamada do desceheap. Quantas chamadas do desceheap foram feitas neste caso?
2. Escreva, sem olhar nas suas notas, uma versão recursiva da função desceheap. Quanto tempo a sua função gasta em função de n?
3. Escreva uma função sobeheap(v,n,i) que recebe um heap v com n elementos possivelmente estragado apenas na posição i, onde foi colocado um elemento com chave maior que o que estava lá (ou a chave do elemento que estava lá foi aumentada). A sua função deve restaurar o heap e deve ser o mais eficiente possível. Quanto tempo a sua função gasta em função de n?
4. Escreva uma função insereheap(v,n,x) que recebe um heap v com n elementos e insere um elemento com chave x no heap. Quanto tempo a sua função gasta em função de n? Dica: Use a função sobeheap(v,n,i).