Universidade Federal do Paraná
Departamento de Informática
Disciplina CI1056 - Algoritmos e Estruturas de Dados II
2o Período do BCC, IBM, MI
Prof. Elias P. Duarte Jr.

Trabalho Prático (2026): VoeHeap: Embarque Aéreo com Prioridade

Data Máxima de Entrega: 30 de outubro de 2026 -> são 3 semanas de prazo, organize-se!

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP ALGORITMOS II 2026" -- máximo cuidado para enviar exatamente este subject, OK?

OBS.: O trabalho deve ser feito em dupla; os dois membros da equipe devem se reunir para fazer todo o código!

A companhia aérea VoeHeap adotou uma nova estratégia para embarque em suas aeronaves. Cada passageiro recebe um número correspondente à sua prioridade, não há grupos de prioridade e sim prioridades individuais.

Programe uma Fila de Prioridades para a VoeHeap implementando o Tipo Abstrato de Dados Heap. Cada passageiro tem cadastrado nome e prioridade. As operações que devem ser disponibilizadas incluem: InicHeap, InsereHeap, RemoveHeap, Heapfy, ChecaHeap, ImprimeHeap, HeapSort (entre outras que forem necessárias). O sistema aloca os passageiros no Heap atribuindo um número aleatório de prioridade para cada um, entre 1 e N, sendo N a capacidade do avião sendo embarcado em número máximo de passageiros. Mostre a ordem em que os passageiros são embarcados e removidos do Heap com RemoveHeap. Permita a qualquer momento a impressão dos passageiros que ainda devem ser embarcados com ImprimeHeap. Permita também a execução do HeapSort e impressão do vetor ordenado. que ordene todos os pacientes de acordo com sua prioridade.

O Heap deve ser implementado em vetor, exatamente como foi visto em sala de aula. Quando executar as funções Heapfy e HeapSort deve ser reportado o número de comparações e trocas de elemento de posição que foram executadas. No Relatório descreva todas as operações implementadas. Explique sua implementação das operações, em particular a operação RemoveHeap. Faça uma interface caprichada (menu de opções) para o usuário do seu sistema!

Implemente também os algoritmos de ordenação QuickSort e InsertSort. Implemente o QuickSort usando como pivô o elemento que é a mediana entre o primeiro, meio e último elementos do (sub-)vetor. Faça uma opção no menu para gerar um vetor de números aleatórios com 1024 elementos e mostre a comparação do HeapSort com o QuickSort e o InsertSort. Qual foi melhor na prática? Para cada algoritmo mostre o número de comparações e trocas de elemento de lugar.

Deve ser construída uma página Web, que contém em documentos HTML, os seguintes itens:

  • Relatório de como foi feito o trabalho e quais foram os resultados obtidos. Use desenhos, diagramas, figuras, todos os recursos que permitam ao professor compreender como a dupla estruturou o trabalho e quais resultados obteve.
  • Listagem do programa em C; por favor acrescente a terminação ".txt" aos programas fonte na versão disponibilizada na Web, por exemplo: HeapAndQuick.c.txt
  • Log dos testes executados: mostre explicitamente diversos casos testados, lembre-se à a partir desta listagem de testes que o professor vai medir até que ponto o trabalho está funcionando.

    Observações:

  • Não serão aceitos trabalhos impressos, nem em meio ótico/magnético.
  • Todos os trabalhos serão defendidos no laboratório, portanto certifique-se que seu trabalho funciona aqui!

    Importante: capriche na legibilidade e organização.

    Prof. Elias P. Duarte Jr.     Departamento de Informática     UFPR