File de priorités

L'objectif de cet exercice est de créer une file de priorités à partir d'un tas min implémenté par un type array. Les éléments de la file sont des enregistrements immuables.

type 'a qdata = {valeur: 'a; priorite: int};;
type 'a file_priorites = {mutable taille: int; tas: 'a qdata array};;

1. 1

   Indice

   Utiliser une variable temporaire pour stocker la première valeur avant de mettre à jour les deux cases du tableau.
   Écrire une fonction echanger : 'a array -> int -> int -> unit qui échange les éléments aux indices i et j du tableau t. Par exemple echanger [|1; 2; 3|] 0 2 renvoie [|3; 2; 1|].
2. 2

   Indice

   Comparer la priorité courante avec celle du parent et effectuer une récursion sur l'indice parent si l'échange est requis.
   Écrire une fonction faire_monter : 'a qdata array -> int -> unit qui fait remonter l'élément à l'indice k vers la racine pour respecter la propriété de tas minimum. Par exemple faire_monter [|{valeur=1; priorite=5}; {valeur=2; priorite=3}|] 1 renvoie [|{valeur=2; priorite=3}; {valeur=1; priorite=5}|].
3. 3

   Indice

   Identifier le fils de priorité minimale puis effectuer une récursion sur son indice tant que la propriété du tas est violée.
   Écrire une fonction faire_descendre : 'a qdata array -> int -> int -> unit qui fait descendre l'élément à l'indice k vers les feuilles pour respecter la propriété de tas minimum. Par exemple faire_descendre [|{valeur=1; priorite=3}; {valeur=2; priorite=5}; {valeur=3; priorite=4}|] 3 0 renvoie [|{valeur=1; priorite=3}; {valeur=3; priorite=4}; {valeur=2; priorite=5}|]. Le premier paramètre entier est la taille de la file et le second l'indice k.
4. 4

   Indice

   Allouer un tableau pré-rempli avec Array.init et initialiser la taille de la structure à zéro.
   Écrire une fonction creer_file_priorites : int -> 'a * int -> 'a file_priorites qui renvoie une file de priorités vide de taille n pré-remplie avec la valeur v et la priorité p. Par exemple creer_file_priorites 3 (0, 1) renvoie {taille=0; tas=[|{valeur=0; priorite=1}; {valeur=0; priorite=1}; {valeur=0; priorite=1}|]}.
5. 5

   Indice

   Placer l'élément à la fin du tableau puis appeler la fonction de remontée avant d'incrémenter la taille logique.
   Écrire une fonction inserer : 'a file_priorites -> 'a * int -> unit qui insère l'élément de valeur v et de priorité p dans la file de priorité filep. Par exemple inserer f (10, 2) modifie la file en place et insère l'élément à la bonne place selon la priorité.
6. 6

   Indice

   Sauvegarder la racine, remplacer son contenu par le dernier élément puis appeler la fonction de descente avant de retourner la valeur sauvegardée.
   Écrire une fonction retirer_minimum : 'a file_priorites -> 'a qdata qui renvoie l'élément de priorité minimale dans la file de priorité filep. Par exemple retirer_minimum f renvoie {valeur=42; priorite=1}.