algorithm - 实现智能列表

Question

我被要求设计一个名为 clever-list 的数据结构，它保存具有真实键号的项目并提供下一个操作:

Insert(x) - 向列表中插入一个新元素。应该在 O(log n) 中。

移除最小值/最大值 - 移除并返回列表中的最小值/最大值元素。应该在 O(log n) 时间内。

Transform - 更改 remove min/max 的返回对象(如果是 min 则为 max，反之亦然)。应该在 O(1) 中。

Random sample(k) - 返回从列表中随机选择的 k 个元素(k 大于 0 且小于 n)。应该在 O(min(k log k, n + (n-k) log (n-k))).

关于结构的假设:数据结构在任何阶段都不会容纳超过 3n 个元素。我们不能假设 n=O(1)。我们可以使用 Random() 方法，它在 O(1) 时间内返回一个介于 [0,1) 和预成型之间的实数。

我设法实现了前三种方法，使用最小-最大精细堆。但是，在这个时间限制内，我对 random sample(k) 方法一无所知。我能找到的只有“Reservoir sampling”，它在 O(n) 时间内运行。

有什么建议吗？

Answer 1

您可以使用在数组中实现的最小-最大堆来完成所有这些操作，包括随机采样。

对于随机抽样，从 0 到 n 中选择一个随机数。那是您要删除的项目的索引。复制该项目，然后用数组中的最后一项替换该索引处的项目，并减少计数。现在，根据需要将该项目冒泡或筛选。

如果它处于最小级别并且该项目小于其父项，则将其冒泡。如果它比最小的 child 大，则将其筛选。如果它处于最高水平，则逻辑相反。

那个随机抽样是 O(k log n)。也就是说，您将从 n 项的堆中删除 k 项。它的复杂性与调用 delete-min 的 k 次相同。

附加信息

如果您不必从列表中删除项目，则可以通过从数组中选择 k 索引在 O(k) 中进行简单的随机抽样。但是，有可能出现重复。为避免重复，您可以这样做:

当你随机选择一个项目时，将它与数组中的最后一个项目交换并将计数减 1。当你选择了所有项目时，它们在最后 k数组的位置。这显然是一个 O(k) 操作。您可以复制要由函数返回的那些项目。然后，将计数设置回原始值并调用您的 MakeHeap 函数，该函数可以在 O(n) 中从任意数组构建堆。所以你的操作是 O(k + n)。

MakeHeap 函数非常简单:

for (int i = count/2; i >= 0; --i)
{
    SiftDown(i);
}

另一种选择是，当您进行交换时，将交换操作保存在堆栈上。即保存 from 和 to 索引。要放回元素，只需以相反的顺序运行交换(即从堆栈中弹出，交换元素，然后继续直到堆栈为空)。选择的时间复杂度为 O(k)，放回的时间为 O(k)，堆栈的额外空间为 O(k)。

当然，另一种方法是按照我的建议进行删除，完成所有删除后，将项目重新插入堆中。这是 O(k log n) 的删除和 O(k log n) 的添加。

顺便说一句，您可以通过使用哈希表来保存随机选择的索引，在 O(k) 最佳情况下进行随机抽样。您只需生成随机索引并将它们添加到哈希表(不接受重复项)，直到哈希表包含 k 项。这种方法的问题在于，至少在理论上，算法可能无法终止。