arrays - 如何设计插入到无限数组

Question

问题陈述

假设我们有一个无限数组，我们在其中存储整数。当数组中有 n 个元素时，只有 n 个单元格被使用，其余为空。

我正在尝试提出一种数据结构/算法，它能够:

• 检查元素是否被存储
• 如果尚未存储则插入一个新元素
• 删除存储的元素

每个操作都必须在 O(sqrt(n)) 中。

方法一

我遇到了 this site ，其中提出了以下算法:

• 数组(实际上，想象一下)分成子数组。它们的长度为 1、4、9、16、25、36、49 等。最后一个子数组不是一个完美的正方形 - 它可能没有完全填满。
• 假设，当我们将这些子数组视为集合时 - 它们按递增顺序排列。因此，更靠右的堆中的所有元素都大于其左侧堆中的任何元素。
• 每个这样的子数组代表一个二叉堆。最大堆。
• 查找:转到堆的第一个索引(又是 1、4、9、16，...)，只要找到第一个堆的最大值(最大值存储在这些索引中)大于你的号码。然后检查这个子数组/堆。
• 插入:完成查找后，将元素插入堆中应有的位置。当堆满时 - 取出最大的元素并将其插入下一个堆。等等。

不幸的是，这个解决方案是O(sqrt(n) * log(n))。

如何让它成为纯粹的O(sqrt(n))？

想法2

由于所有操作都需要执行查找，我想插入和删除都是 O(1)。只是一个猜测。并且可能一旦插入完成，删除将是显而易见的。

澄清

What does the infinite array mean?

基本上，您可以在其中存储任意数量的元素。它是无限的。但是，有两个限制。第一 - 一个单元格只能存储一个元素。其次 - 当数组存储当前 n 个元素时，只能使用前 n 个单元格。

What about the order?

没关系。

Answer 1

您是否考虑过 bi-parental heap (又名:BEAP)？

堆保持sqrt(n)的高度，也就是说insert，find，remove都运行在O(sqrt(n))的最坏情况下案例。

Munro 和 Suwanda 1980 年的论文 Implicit data structures for fast search and update 中描述了这些结构.