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

Question

我有一套 S T 类型的元素.有部分订单<=在 T 类型的元素上.众所周知，S 中的所有元素没有订购。然后，我需要一种方法来执行以下查询:having element e类型 T , 找到 e'在 S这样 e <= e' .

是否有一种数据结构可以有效地执行此类查询(无需对 S 进行线性扫描)？

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

Answer 1

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

此外，您还可以根据子集中每个元素大于的元素数(按降序)对子集进行排序。并按顺序扫描元素。