Implémentations naïves

Une première idée serait d'implémenter une file de priorité avec un tableau non trié. Dans ce cas, on a :

• Extraction du plus petit élément en $\mathcal {O}(n)$
• Ajout d'un élément en $\mathcal {O}(1)$
• Suppression du plus petit élément $\mathcal {O}(n)$

Cette solution est peu satisfaisante. Avec un tableau trié, une liste chaînée triée ou non, on obtient des résultats peu satisfaisants. Nous allons devoir méditer sur des solutions permettant d'obtenir des temps de calcul au moins inférieurs à $\mathcal{O}(log_2 n)$.