数据结构，以支持一组二维的特定查询点

我有一组2D点，我希望能够做下面的查询与参数x_min和n：什么是n点与最大y这有x > x_min？数据结构，以支持一组二维的特定查询点

要改写在Ruby中：

class PointsThing 
    def initialize(points) 
    @points = points 
    end 

    def query(x_min, n) 
    @points.select { |point| point.x > x_min }.sort_by { |point| point.y }.take(n) 
    end 
end

理想的情况下，我班也将支持插入和删除操作。

我不能想到一个数据结构，这将使查询运行时间小于O（| @points |）。有人知道吗？

来源

2015-07-01 Buck Shlegeris

所有的n点如何能有最大的y？ –

你是否意味着这n个点的y坐标将大于其余点。 –

我的意思是，如果你按'y'降序排序，则第一个'n'分。 –

按x降序对点进行排序。对于每个点的顺序，将其插入到按y降序排列的purely functional红黑树中。将所有中间树都保存在一个数组中。

要查找特定的x_min，请使用二分查找来查找中间树，其中插入了x> x_min的点。遍历这棵树找到前n个点。

预处理成本为O（p log p）时间和空间，其中p是点数。查询时间是O（log p + n），其中n是要在查询中返回的点数。

来源

2015-07-01 13:05:44

这并不涉及我可以添加或删除项目的情况，但仍然是最佳答案。 –

如果你的数据没有排序，那么你别无选择，只能检查每个点，因为你不知道是否存在另一个点，其中y大于所有其他点的点，并且其中x > x_min。简而言之：如果你没有全部检查，你不知道是否应该包括另一点。

在这种情况下，我会假设根据您的要求检查sub子线性时间是不可能的，因为您必须全部检查它们。搜索全部的最佳案例将是线性的。

如果你的数据是排序的，那么你的最好情况将是恒定时间（所有n点是那些y最大），最坏情况将是线性的（所有n点是那些y最少）。如果你的x和x_min在一个特定的范围内都是大致随机的，平均情况会更接近常数。

如果您希望按比例缩放（也就是说，您可能拥有较大的n值），您还是希望保持结果集的排序顺序，因为您需要检查新的潜在点并将其降到最低点插入时的值（如果大小> n）。使用树，这可以是日志时间。

因此，要做到这一点，最糟糕的情况是未排序的点，在这种情况下，您正在查看nlog（n）时间。排序点更好，在这种情况下，您正在查看log（n）时间的平均情况（再次假设x和x_min的值大致随机分布），其中yes为次线性。

如果它是不是第一个明显的原因排序点都会有有一定的时间进行搜索，我将在这里很快走了过来。

如果y值最大的n个点都有x > x_min（最好的情况），那么你只是抓住了你需要的顶部，所以这种情况是显而易见的。

对于平均情况，假设大致随机分布的x和x_min，x > x_min基本上是一半的几率。对于任意两个随机数a和b，a > b与b > a的可能性相同。这与x和x_min是一样的; x > x_min与x_min > x的可能性相同，意味着0.5概率。这意味着，对于您的积分，平均每查看第二个积分就会满足您的x > x_min要求，所以平均而言，您将检查2n积分以找到符合您标准的n个最高积分。所以最好的情况是c时间，平均值2c仍然是不变的。

但是，请注意，对于接近集合大小的n值，这隐藏了您正在经历整个集合的事实，基本上使其回到线性时间。因此，如果你假定在你的集合的大小范围内的n的随机值，我认为它是恒定的时间不成立。

如果这不是纯粹的学术问题，而是由一些实际需要引起的，那么这取决于具体情况。

（编辑）我刚才意识到，我的常数时间断言假设一个数据结构，您可以直接访问最高值，并可以按顺序访问较低的值。如果提供给您的数据结构不符合该描述，那么很明显情况并非如此。

来源

2015-07-01 06:21:55 Loduwijk

一些预计算将有助于在这种情况下。

第一个分区将x_min作为主元素。

然后对于一套躺在x_min构建基于y坐标一个max_heap的右侧点。

现在运行您的查询为：在构建的max_heap上执行n个extract_max操作。

您的查询的运行时间将日志X +日志（X-1）+ ...日志（X-（N-1））

日志X：对于首先提取最大操作。

log X-1：对于第二次提取max操作等。

X：原始最大堆的大小。

即使在最坏的情况下，当你ň< < X，采取将O（N日志X）的时间。

来源

2015-07-01 06:35:32

公平地说 - 划分和构建max_heap需要考虑复杂性，因为它们取决于参数之一（'x_min'）。因此，在最坏的情况下，你建议的解决方案会在'O（n^2）'中运行，不是吗？ –

@HW我亲爱的朋友，构建堆和分区的时间复杂度是线性的，即O（n），其中n是输入大小。 –

公平点，出于某种原因，我将这与大卫方法，这将包括建立堆几个x_min值。 –

符号

让P是点的集合。

让top_y (n, x_min)描述查询以收集P中的n点，其中x坐标大于或等于'x_min'的坐标中的y坐标最大。

让x_0为点集中x坐标的最小值。将x_0右侧的x轴划分为一组左边的闭合右侧开放区间I_i，其由点集P的x坐标组成，使得min(I_i)是i，但是是P的最小x坐标。定义x的坐标等级r(x)，因为间隔x的索引是x < x_0的元素或0。

请注意，r(x)可以使用二叉查找树在O(log #({I_i}))中计算。

简单的解决方案

排序你的观点通过降低y坐标设置和保存这个数组A在时间O(#P log #P)和空间O(#P)。
过程每个查询top_y (n, x_min)通过按顺序遍历该阵列中，跳过的项目A_i: A_i.x < x_0，计数所有其它条目，直到计数器达到n或者你是在A结束。此处理需要O(n)时间和O(1)空间。

注意，这可能已经足够了：查询top_y (n_0, a_0); a_0 < min { p.x | p \in P }, n_0 = c * #P, c = const要求第1步反正和n << #P和“罕见”查询任何进一步的优化是不值得的努力。

观察

考虑序列s_i, S_第（i + 1）of points with x-coordinates greater than or equal to分钟（I_I），分钟（I_（I + 1））, ordered by decreasing y-coordinate. S_第（i + 1）is a strict subsequence of s_i`。
如果p_1 \in s_(i+1)和p_2.x >= p_1.x则p_2 \in s_(i+1)。

精解

提炼数据结构允许O(n) + O(log #P)查询处理时间。

从简单的解决方案注释数组A，使用“后继调度”为那些元素A_i与A_(i+1).x < A_i.x;该调度数据将包含的数组disp:[r(A_(i+1).x) + 1 .. r(A_i.x)] - A中下一个元素的索引，其x坐标至少与disp中的索引一样高。给定的调度指数足以处理查询，因为...

... disp[j] = disp[r(A_(i+1).x) + 1]每个j <= r(A_(i+1).x)。
...与r(x_min) > r(A_i.x)任何x_min，算法就不会在这里

正确的索引来访问disp是r(x_min)这仍然是整个查询常量，因此需要O(log #P)而计算每一次查询索引选择本身在每个A元素处为O(1)。

disp可以预先计算。整个disp阵列中没有两个disp条目是相同的（证明跳过了，但很容易[;-)]看到给定的结构）。因此，disp阵列的构建可以通过在A中排序的点集在单次扫描中执行基于堆栈。由于有#P个条目，disp结构需要O(#P)空间和O(#P)时间来构建，主要由y排序的空间和时间要求。所以从某种意义上说，这种结构是免费的。

查询top_y(n,x_min)

计算r(x_min)时间要求：O(log #P);
穿过A：O(n);

来源

2015-07-01 09:41:24 collapsar

数据结构，以支持一组二维的特定查询点

回答

相关问题