algorithm - 在偏序集中查找大于给定的元素

Question

我有一组S类型的元素T。<=type 的元素有一个偏序T。众所周知，其中的所有元素S都不是有序的。然后，我需要一种方法来执行以下查询：拥有type的元素，找到这样的eTe'Se <= e'.

是否有允许有效执行此类查询的数据结构（无需线性扫描S）？

重要提示：T是完整的格子。

Answer 1

您可以预处理列表并找到没有任何其他元素大于这些数字的元素子集（假设您将所有数字表示为 dag，您应该找到所有没有父元素的元素）。一旦你有了那个子集，你需要做的就是对这个子集进行线性扫描。我不认为你能做得比这更好。

此外，您还可以按子集中每个元素大于的元素数量（按降序排列）对该子集进行排序。并按顺序扫描元素。