File de priorité Dijkstra

Salut a tous,
pour un projet de fac je suis sencé implementer l'algorithme de Dijstra en C de manière efficace, ce qui implique
d'utiliser une file de priorité.
Je voulais au départ implementer la file avec un tas binaire (tableau de binome element/clé, dont l'ordre est donné par la place au sein du tableau) mais je me suis retrouvé confronté a un problème :
lorsqu'on relaxe une arette du graphe, on doit mettre a jour la clé de l'element dont le poid change, ce qui implique :
1 - de trouver l'element dans le tas
2 - de changer sa clé
3 - de le faire remonter dans le tas
les étapes 2 et 3 sont implementés sans souci, la ou je bloque c'est a l'etape 1 : une recherche directement dans le tableau me donne une complexité en O(n), mais j'ai le sentiment qu'il doit y avoir un moyen bien plus efficace d'effectuer la recherche, quelqu'un aurait des solutions/idées a me proposer a ce sujet ?

Merci d'avoir lu, j'espère que vous pourrez m'aider

Il s'agit d'un arbre non trié car si je comprend bien ce sont des distances. A part une recherche dichotomique qui requiert une arbre trié, je ne pense pas que tu puisse aller plus vite qu'en O(n).
A ma connaissance il faut que ton tas soit trié pour que tu ais une performance en O(log n). ^^