Quelle structure de données persistante pour un ensemble d'éléments partiellement ordonnés?

J'ai besoin de stocker des ensembles d'éléments de type a. Le type a est partiellement ordonné, donc comparer et un 2 peut retourner plus petit, plus grand, égal ou incomparable.$a_1$$a_2$

Un problème avec les tables de hachage est que deux éléments égaux peuvent être représentés différemment, et je n'ai pas accès à une fonction de hachage compatible avec l'égalité.

La comparaison de deux éléments peut être un processus long, il serait donc intéressant de minimiser les comparaisons. Si nécessaire, il est possible de mémoriser les appels à l'opérateur de comparaison. Je me rends compte maintenant que je n'aurai besoin que de stocker des antichaines (ou supposons-le). Plus précisément, les opérations que je devrai effectuer sont les suivantes:

• Retirez un élément de l'antichaîne;
• Essayez d'ajouter un élément. Si l'élément est plus petit qu'un membre, ne l'ajoutez pas, sinon, ajoutez-le et supprimez chaque élément plus petit que lui.

Je peux également délimiter chaque élément par deux entiers, de sorte que si je sais que et i 3 < b < i 4 , alors connaître i 2 < i 3 me donne instantanément a < b . Bien sûr, i 2 ≮ i 3 ne signifie pas a ≮ b ... Trouver des bornes entières est une opération relativement bon marché par rapport à une comparaison complète d'éléments.$i_1 < a < i_2$$i_3 < b < i_4$$i_2 < i_3$$a < b$$i_2 \not< i_3$$a \not < b$

L'article "Tri et sélection dans les PoSets" de Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 qui décrit une représentation dynamique des PoSets basée sur des antichaînes.

Vous pourriez également être intéressé par l'article "Succinct Posets" de Munro, Nicholson, 2012 récemment publié sur Arxiv et par la bibliographie qui s'y trouve. Leur structure de données est statique mais je suppose que la prochaine étape est d'avoir une structure de données dynamique.

$O(\lg n)$