Comment créer une structure de données avec des limites d'exécution

Question

Je dois implémenter une structure de données qui supporte la suppression d'insertion et rechercher dans O (log (n)) et extraire un objet spécial dans O (1). Ma structure de données doit contenir les véhicules triés par leur ID et chaque véhicule a un champ qui représente le temps jusqu'au prochain service. J'ai besoin d'extraire les véhicules qui devaient être les services suivants dans O (1). Toutes les suggestions sont les bienvenues. J'ai compris que j'avais besoin de deux structures de données séparées et j'ai pensé à avoir 1 jeu et 1 file d'attente prioritaire tous les deux triés par d'autres paramètres mais en gardant la copie du même pointeur. Le problème que j'ai, c'est que lorsque j'essaie de supprimer de la structure "set", je reste avec la poubelle sur l'autre structure de données (file d'attente prioritaire).

Answer 1

Une table de hachage prend en charge l'insertion, la suppression et la recherche beaucoup mieux que O (log (n)). C'est en supposant que vous n'avez jamais à refaire tout ce que vous faites quand vous faites pousser la table. La partie difficile serait de localiser le "prochain" véhicule en O (1) temps. En fonction de l'implémentation, un min heap vous donnera l'insertion O (1) et O (log (n)) (amortie), et la recherche de l'élément minimum est O (1). Supprimer un élément du tas est une opération O (log (n)), mais trouver un élément arbitraire dans le tas est plus de O (log (n)).

Si je devais l'implémenter, j'utiliserais deux structures de données distinctes: une table de hachage et un tas min. Le raisonnement est que la table de hachage offre une insertion, une suppression et une recherche très rapides, et que le segment de mémoire fournit un ordre basé sur le temps de service. Le seul endroit où cela ne répond pas à vos exigences est la suppression d'un véhicule, car cela nécessite de rechercher le tas pour un élément arbitraire. En fait, il serait possible, bien que probablement désordonné, de combiner les deux structures de données de sorte que votre table de hachage stocke des objets de nœud de tas (qui ont une référence aux données réelles) plutôt que les objets de données réels. Tant que le nœud de tas sait où il se trouve dans le tas (c'est-à-dire qu'il possède un pointeur parent et des pointeurs enfants gauche et droit), vous pouvez utiliser la table de hachage pour trouver un nœud et supprimer ce nœud du tas.