Quelle est la complexité temporelle nécessaire pour extraire un élément d’une file d’attente prioritaire ?

* Tas binaire :

* O(log n) . Il s’agit de l’implémentation la plus courante et la plus efficace. La suppression de la racine (élément de priorité la plus élevée) prend O(1). Cependant, vous devez ensuite remplacer la racine par le dernier élément du tas et "tassez vers le bas" pour restaurer la propriété du tas. Cette opération de tas prend un temps O (log n), où n est le nombre d'éléments dans le tas.

* Arbre de recherche binaire (BST) :

* O(log n) dans le cas moyen pour un BST équilibré (comme un arbre AVL ou un arbre rouge-noir). Trouver le maximum (ou le minimum, selon la priorité) est O(log n), et le supprimer est également O(log n).

* O(n) dans le pire des cas pour un BST déséquilibré. Si l'arborescence est asymétrique (par exemple, ressemble à une liste chaînée), la recherche et la suppression du maximum/minimum peuvent prendre un temps linéaire.

* Tableau ou liste chaînée (non ordonnée) :

* O(n) . Vous devez parcourir toute la liste pour trouver l’élément ayant la priorité la plus élevée, puis le supprimer.

* Tableau ou liste chaînée (ordonnée) :

* Si trié par priorité (par exemple, tableau trié) :l'affichage de l'élément avec la priorité la plus élevée (probablement à la fin ou au début, selon l'ordre) peut être O(1). Cependant, si vous utilisez un tableau trié et que vous devez conserver l'ordre de tri après avoir supprimé l'élément, vous devrez peut-être décaler les éléments, ce qui entraînera O(n) dans le pire des cas. Les listes chaînées peuvent éviter le déplacement, donc l'affichage est O(1) si vous savez où se trouve l'élément la plus prioritaire, mais le trouver était toujours O(n) pour commencer.

* Tas de Fibonacci :

* O(log n) temps amorti. Les tas de Fibonacci sont plus complexes à mettre en œuvre, mais ils offrent théoriquement de meilleures performances pour certaines opérations, en particulier lorsque vous avez de nombreuses opérations de « diminution de clé ». « Amorti » signifie que même si les opérations individuelles peuvent prendre plus de temps, la complexité temporelle moyenne d'une séquence d'opérations est de O (log n).

Résumé :

| Mise en œuvre | Complexité temporelle (Popping) |

| ------------------------------------ | ----------------------- |

| Tas binaire | O(logn) |

| BST équilibrée | O(logn) |

| BST déséquilibré | O(n) |

| Tableau/Liste non ordonné | O(n) |

| Tableau/Liste ordonné | O(1) ou O(n) |

| Tas de Fibonacci | O(log n) (amorti) |

En pratique :

L'implémentation la plus courante pour les files d'attente prioritaires est le tas binaire. , en raison de ses bonnes performances (O(log n)) et de sa mise en œuvre relativement simple. Par conséquent, vous pouvez généralement supposer que la complexité temporelle de l'extraction d'une file d'attente prioritaire est O(log n) sauf si la documentation ou le contexte spécifie explicitement une structure de données sous-jacente différente.