INF1010 - Listas de prioridades, heaps e heapsort

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

1. Complete o módulo listaprio.c completando a função interna listap_monta e usando-a para implementar o caso em que a função listap_cria recebe um array inicial de prioridades. (A construção deve seguir os passos indicados nos slides Altere o programa de testes para testar essa nova funcionalidade.
2. (***) Agora implemente um heapsort, uma forma de ordenação que usa a lista de prioridades. A função heapsort (e heapsort2) já está esboçada no arquivo. Implemente a função cria_listaordenada, que recebe uma lista de inteiros e usa uma lista de prioridades para criar uma lista contendo os inteiros da lista inicial ordenados em ordem decrescente:

   Sua implementação deve criar uma lista de prioridades e depois usar a idéia dada em sala para transformar a lista de prioridades em um array ordenado. Cuidado com o uso de memória: Verifique o que vc deve liberar e o que vc deve retornar ao final de cria_listaordenada.

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

3. A função heapsort usa listap_cria já passando o array inteiro de números, usando sua implementação do item 1, enquanto a heapsort2 faz a inserção um a um. Caso você verifique que sua função está correta, vamos fazer algumas medidas. O programa lpmede.c contém um esqueleto que lê dados de um arquivo chamado entrada e mede os tempos de ordená-lo usando (1) a função de quicksort da biblioteca padrão de C e (2) a sua função de ordenação.