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
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 :