Implémentations

N'importe quel arbre équilibré peut être utilisé pour implémenter une file de priorité, mais ce type d'implémentation n'est pas très économique, ni en consommation de mémoire, ni en temps d'exécution. De plus, ces solutions font que le ramasse-miettes doit parcourir un grand nombre d'objets.

La solution la plus adaptée est le tas (voir section 23.4.3) codé sous forme de vecteur. De cette façon, les deux opérations principales ont une complexité de $O(\texttt{log} n)$ au pire. L'insertion et la suppression dans un tas sont beaucoup plus rapides que dans un arbre équilibré. De plus, le surcoût en mémoire est minimal grâce au codage sous forme de vecteur. Le code de la section 23.4.3 utilise à son tour le code de la section 23.3.2 qui sera nécessaire pour la création de la file de priorité.

Voici le code :

file-de-priorite.lisp