algorithm - 存在某种数据结构

Question

我想知道，在以下条件和时间下是否存在这样的数据结构(可能很复杂)？

如果我们获得一个未排序的列表 L 并从中构建一个数据结构，如下所示:

• Build(L,X) - 在 O(n) 时间内，我们从 n 个元素的未排序列表构建结构 S
• Insert (y,S) under O(lg n) 我们将z插入到结构S中
• DEL-MIN(S) - 在 O(lg n) 下，我们从 S 中删除最小元素
• DEL-MAX(S) - 在 O(lg n) 下，我们从 S 中删除最大元素
• DEL-MId(S) - 在 O(lg n) 下，我们从 S 中删除上部内侧(天花板函数)元素

问题是列表 L 是未排序的。可以存在这样的数据结构吗？

Answer 1

DEL-MIN 和 DEL-MAX 很简单:保留所有元素的最小堆和最大堆。唯一的技巧是您必须在堆中保留值的索引，这样当(例如)您删除最大值时，您也可以在最小堆中找到它并将其删除。

对于 DEL-MED，您可以保持元素的最大堆小于中值，元素的最小堆大于或等于中值。完整的描述在这个答案中:Data structure to find median .请注意，在该答案中返回了地板中位数，但这很容易修复。同样，您需要像第一部分一样使用交叉索引技巧来引用其他数据结构。如果在您的问题表述中可能的话，您还需要考虑如何处理重复的元素。 (如有必要，您可以通过将重复元素存储为堆中的 (count, value) 来实现，但这会使插入/删除时重新平衡堆变得复杂一点)。

这一切都可以在 O(n) 中构建吗？是的——您可以在 O(n) 时间内找到 n 个事物的中位数(使用中位数算法)，并且可以在 O(n) 时间内构建堆。

总的来说，数据结构是 4 个堆(一个所有元素的最小堆，一个所有元素的最大堆，一个 floor(n/2) 最小元素的最大堆，一个最小堆ceil(n/2) 个最大的元素。所有元素都具有彼此的交叉索引。