INF1010 - Listas de prioridades, heaps e heapsort

Entrega: até segunda, dia 21/10, às 23h

Em sala, discutimos a implementação de listas de prioridades usando heaps. O módulo heap.c implementa quase toda a interface descrita em heap.h (e debug.h). O arquivo lpteste.c contém um teste inicial desse módulo.

1. Complete o módulo heap.c, terminando a implementação da função interna heap_monta e usando-a para implementar o caso em que a função heap_cria recebe um array inicial de prioridades (a construção deve seguir os passos indicados nos slides). Altere o programa de teste para testar essa nova funcionalidade.
2. Agora implemente um heapsort. A função heapsort já está esboçada no arquivo; você deve implementar a função cria_listaordenada, que recebe uma lista de prioridades (um heap) e a utiliza para criar um vetor contendo os inteiros da lista inicial, ordenados em ordem decrescente.

   Note que, ao invés de inserir os elementos removidos do heap no final da lista de prioridades, vc deve colocá-los no vetor ordenado!

   Modifique o programa de teste para verificar sua função de ordenação.

Entregue os arquivos heap.c e lpteste.c e indique na área de texto da tarefa quais funções você implementou.