Implémentation de la file d'attente prioritaire en utilisant le tas maximum par rapport au BST équilibré
Balanced BST et max heap effectuent tous deux l'insertion et la suppression dans O(logn). Cependant, trouver la valeur maximale dans un tas max est O(1)mais c'est O(logn)dans BST équilibré.
Si nous supprimons la valeur max dans un tas max, cela prend O(logn)car il s'agit d'une opération de suppression.
En BST équilibré, suppression de l'élément max = recherche de la valeur maximale + suppression; il est égal à logn + logn réduit à O(logn). Donc, même la suppression de la valeur maximale dans BST équilibré est O(logn).
J'ai lu une telle application de tas max est une file d'attente prioritaire et son objectif principal est de supprimer la valeur maximale pour chaque opération de retrait de la file d'attente . Si la suppression de l'élément max concerne O(logn)à la fois le tas max et le BST équilibré, j'ai les questions suivantes
Quel est le but d'un tas max dans la file d'attente prioritaire simplement parce qu'il est facile à implémenter plutôt que d'utiliser un BST équilibré entièrement interrogeable?
Puisqu'il n'y a pas de calcul du facteur d'équilibrage, le tas maximum peut être appelé un arbre binaire déséquilibré?
Chaque BST équilibré peut être utilisé comme une file d'attente prioritaire et qui peut également être recherchée,
O(logn)mais la recherche de tas max estO(n)correcte?
Toutes les complexités temporelles sont calculées pour le pire des cas. Toute aide est grandement appréciée.
Réponses
Quel est le but d'un tas max dans la file d'attente prioritaire simplement parce qu'il est facile à implémenter plutôt que d'utiliser un BST équilibré entièrement interrogeable?
Certains avantages d'un tas sont:
Dans une série d'entrée non triés, un tas peut encore être construit en O (n) temps , tandis qu'un BST a besoin de O (nlogn) temps .
Si l'entrée initiale est un tableau, ce même tableau peut servir de tas, ce qui signifie qu'aucune mémoire supplémentaire n'est nécessaire pour cela. Bien que l'on puisse penser à des moyens de créer un BST en utilisant les données en place dans le tableau, ce serait assez étrange (pour les types primitifs) et donnerait plus de temps de traitement. Un BST est généralement créé à partir de zéro, copiant les données dans les nœuds au fur et à mesure de leur création.
Fait intéressant: un tableau trié est aussi un tas, donc si l'on sait que l'entrée est triée, il n'y a rien à faire pour construire le tas.
Un tas peut être stocké sous forme de tableau sans avoir besoin de stocker des références croisées , tandis qu'un BST se compose généralement de nœuds avec des références gauche et droite. Cela a au moins deux conséquences:
- La mémoire utilisée pour un BST est environ 3 fois supérieure à celle d'un tas.
- Bien que plusieurs opérations aient la même complexité de temps pour le tas et le BST, la surcharge pour adapter un BST est beaucoup plus grande, de sorte que le temps réel passé sur ces opérations est un facteur (constant) plus grand dans le cas BST.
Puisqu'il n'y a pas de calcul du facteur d'équilibrage, le tas maximum peut être appelé un arbre binaire déséquilibré?
Un tas est en fait un arbre binaire complet , il est donc toujours aussi équilibré que possible: les feuilles seront toujours positionnées au dernier ou au dernier niveau. Un BST auto-équilibré (comme AVL, rouge-noir, ...) ne peut pas battre ce niveau élevé d'équilibrage, où vous aurez souvent des feuilles se produisant à trois niveaux ou même plus.
Chaque BST équilibré peut être utilisé comme une file d'attente prioritaire et qui est également consultable dans O (logn) mais la recherche de tas max est O (n) correcte?
Oui c'est vrai. Donc, si l'application a besoin de la fonction de recherche, alors un BST est supérieur.
Quel est le but d'un tas max dans la file d'attente prioritaire simplement parce qu'il est facile à implémenter plutôt que d'utiliser un BST équilibré entièrement interrogeable?
Nan. Le tas max s'adapte mieux, car il est soigneusement instrumenté pour renvoyer le prochain élément (en respectant la priorité) dès que possible, en temps O (1). C'est ce que vous attendez de la file d'attente prioritaire la plus simple possible.
Puisqu'il n'y a pas de calcul du facteur d'équilibrage, le tas maximum peut être appelé un arbre binaire déséquilibré?
Nan. Il y a aussi un équilibre. Pour faire court, l'équilibrage d'un tas se fait par des opérations de décalage vers le haut ou vers le bas (permutation des éléments qui sont dans le désordre).
Chaque BST équilibré peut être utilisé comme une file d'attente prioritaire et qui est également consultable dans O (logn) mais la recherche de tas max est O (n) correcte?
Oui! Ainsi qu'une liste liée pourrait être utilisée ou un tableau. Cela va juste être plus cher en termes de notation O et beaucoup plus lent en pratique.