Trouver l'élément plus grand que donné dans l'ensemble partiellement ordonné

Question

J'ai un ensemble S des éléments du type T. Il y a une commande partielle <= sur les éléments de type T. Il est connu que tous les éléments de S ne sont pas commandés. Ensuite, je besoin d'un moyen pour effectuer la requête suivante: élément ayant e de type T, trouver e' dans S tels que e <= e'.

Existe-t-il une infrastructure de données permettant d'effectuer de telles requêtes efficacement (sans balayage linéaire de S)?

Remarque importante: T est un treillis complet.

Answer 1

Vous pouvez prétraiter la liste et trouver un sous-ensemble d'éléments qui n'ont aucun autre élément supérieur à ces nombres (supposons que vous ayez représenté tous les nombres sous forme de dag, vous devriez trouver tous les éléments sans parents). Une fois que vous avez ce sous-ensemble, tout ce que vous devez faire est un balayage linéaire sur ce sous-ensemble. Je ne pense pas que tu puisses faire mieux que ça.

En outre, vous pouvez également trier ce sous-ensemble par le nombre d'éléments de chacun de ces éléments dans le sous-ensemble supérieur à (dans l'ordre décroissant). Et numérisez les éléments dans l'ordre.