Existe-t-il un type de structure de données en forme de set supportant la fusion en O (logn) time et k-th en O (logn) time? (N est la taille de cet ensemble)

Question

Existe-t-il un type de jeu? structure de données supportant la fusion en temps O (logn) et la recherche d'élément k en O (logn) time? n est la taille de cet ensemble.

Answer 1

Si vous souhaitez accepter l'amortissement, vous pouvez atteindre les limites souhaitées de temps O (lg n) pour la fusion et la recherche en utilisant un arbre de recherche binaire pour représenter chaque ensemble. La fusion de deux arbres de taille m et n nécessite un temps O (m log (n/m)) où m < n. Si vous utilisez l'analyse amortie et imputez le coût de la fusion aux éléments du plus petit ensemble, au plus O (lg n) est imputé à chaque élément au cours de toutes les opérations. La sélection du kième élément de chaque ensemble prend aussi l'heure O (lg n).

Je pense que vous pourriez également utiliser une collection de tableaux triés pour représenter chaque ensemble, mais l'argument d'amortissement est un peu plus délicat.

Comme indiqué dans les autres réponses, vous pouvez utiliser des tas, mais obtenir O (lg n) à la fois pour fusionner et sélectionner nécessite un peu de travail.

Answer 2

Vous pouvez essayer un Fibonacci heap qui fusionne en temps amorti constant et diminue la clé en temps amorti constant. La plupart du temps, un tel tas est utilisé pour les opérations où vous tirez plusieurs fois la valeur minimale, donc une fonction de vérification de l'appartenance n'est pas implémentée. Cependant, il est assez simple d'en ajouter un en utilisant la logique de réduction de clé, et en supprimant simplement la partie de diminution.

Answer 3

Si k est une constante, toute meldable heap fera, y compris leftist heaps, skew heaps, pairing heaps et des tas de Fibonacci. Tant la fusion et obtenir le premier élément dans ces structures prennent typiquement O (1) ou O (lg n) amorti temps, de sorte O (k lg n) maximale.

Notez toutefois que l'obtention du k « élément th peut être destructeur dans le sens que les premiers k -1 éléments peuvent être retirés du tas.

Answer 4

arbres doigt peut le faire et quelques autres opérations:

http://en.wikipedia.org/wiki/Finger_tree

Il peut y avoir quelque chose d'encore mieux si vous n'êtes pas limité à des structures de données purement fonctionnelles (c.-à-alias « persistante », où par là signifiait pas "sauvegardé sur un stockage sur disque non volatile", mais "toutes les versions précédentes" de la structure de données sont disponibles même après "ajout" d'éléments supplémentaires ").