Laboratoire 9 : Monceaux / Files prioritaires

Lectures préalables

• Section 9 (Monceau) des notes de cours.

Objectifs

• Implémenter un monceau binaire générique basé sur un tableau dynamique.
• Utiliser le monceau comme file prioritaire pour résoudre un problème simple.
• Comprendre les faiblesses du monceau binaire et connaître des solutions possibles.

Fichiers du lab9

wget http://cria2.uqam.ca/INF3105/lab9/lab9.zip
unzip lab9.zip

Simulation d'un monceau en mémoire

Dessinez la représentation mémoire (pile et tas) d'un monceau après l'insertion (dans cet ordre) des éléments 4, 2, 6, 5, 1, 0, 3.

Implémentation de la classe Monceau

Vous devez compléter l'implémentation de la classe Monceau dans le fichier monceau.h. Vous pouvez utiliser la classe Tableau dans votre implémentation (en substituant le fichier tableau.h fourni par votre implémentation faite au lab3/tp1).

1. Complétez la fonction bool estVide();.
2. Complétez la fonction const T& minimum() const;.
3. Complétez la fonction void inserer(const T&);.
4. Complétez la fonction void enleverMinimum();.

Une fois l'implémentation terminée, vous pouvez vérifier que tout fonctionne correctement en compilant le programme test_monceau.cpp avec la commande make et en l'exécutant avec la commande ./test_monceau.

Résolution d'un problème: Répartition de députés

Plusieurs pays utilisent une méthode de répartition pour déterminer combien de députés chaque province ou chaque parti (dans le cas d'un système proportionnel) obtiendra. Plusieurs méthodes de répartition existent. Aux États-unis, la constitution (Article 1, Section 2) énonce:

Representatives and direct Taxes shall be apportioned among the several States which may be included within this Union, according to their respective Numbers. [...] The Number of Representatives shall not exceed one for every thirty Thousand, but each State shall have at Least one Representative [...].

La méthode de répartition utilisée par le pays (depuis 1941) respectant les contraintes de la constitution est la méthode d'Huntington-Hill. Cette méthode assigne d'abord un représentant (député) à chaque état, puis répartit les députés restants un à un aux états en fonction de la formule de priorité Q = P/sqrt(n*(n+1)), où:

• Q est la priorité d'un état;
• P est la population de l'état;
• n est le nombre de députés déjà assignés à l'état.

Vous devez compléter le programme huntington.cpp qui lit à partir d'un fichier etats.txt la population de chaque état et qui écrit ensuite sur la sortie standard le nombre de députés que chaque état devrait obtenir selon la méthode d'Huntington-Hill. À noter qu'il y a en tout 435 députés à répartir. Le monceau vu en cours et implémenté plus-haut permet de trouver par défaut la valeur la plus petite, alors qu'on s'intéresse ici en priorité à l'état ayant la métrique la plus élevée pour assigner le prochain député. Plusieurs solutions sont possibles pour résoudre ce problème. Par exemple:

• Créer une nouvelle classe Monceau qui offre les opérations const T& maximum() const et void enleverMaximum() plutôt que const T& minimum() const et void enleverminimum();
• Utiliser la classe monceau existante, mais en inversant la relation d'ordre (bool operator<(const T& autre) const) du type T. (solution suggérée)

Résolution d'un problème: File d'attente dans un hôpital

On souhaite compléter le programme hopital.cpp qui permet de gérer une file prioritaire de patients. Ce programme lit un fichier qui contient des « requêtes ». Ces requêtes consistent respectivement à :

• ajouter un patient: ajout <matricule> <priorité>
• retirer et retourner le patient le plus prioritaire: max

Le matricule et la priorité d'un patient sont simplement des nombres entiers. Comme pour le problème précédent, on souhaite encore une fois obtenir les priorités les plus élevées en premier.